韩雪冬网站,链接买卖是什么意思,在线绘画网站,深圳企业网站建设公司排名力扣72. 编辑距离
给你两个单词 word1 和 word2#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作#xff1a;
插入一个字符删除一个字符替换一个字符
解题思路#xff1a;
本题与583. 两个字符串的删除操作其实是一样…力扣72. 编辑距离
给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符
解题思路
本题与583. 两个字符串的删除操作其实是一样的只是583是可以在两个字符串中进行删除而本题只在word1中进行增删改操作这里我们需要对操作进行等价。
在word1中删除元素不用变
在word1中增加元素相当于在word2中删除对应元素
在word1中修改元素相当于同时删除word1和word2中对应的元素元素不同时
动规五部曲
1.dp数组定义和含义
定义二维dp数组大小为word1和word2的大小加1dp[i][j]表示以i-1结尾的word1的子串通过增删改变成word2的以j-1结尾的子串的最小操作数。
2.dp数组递推公式
当word1[i-1]word2[j-1]即比较的字符相同时不需要对word1做任何操作因此dp[i][j]dp[i-1][j-1]。
当word1[i-1]!word2[j-1]即比较的字符不同时我们可以有三种操作
删除word1中对应元素则dp[i][j] dp[i-1][j]1在word1增加一个对应的word2元素相当于删除word2中对应元素则dp[i][j]dp[i][j-1]1改变word1中对应元素为word2对应元素相当于同时删除word1和word2对应元素则dp[i][j]dp[i-1][j-1]1
综上当比较的字符不同时dp[i][j]min{dp[i-1][j],dp[i][j-1],dp[i-1][j-1]} 1. if (word1.charAt(i-1) word2.charAt(j-1)) {// 字符相等不需要删除dp[i][j] dp[i-1][j-1];}else {// 字符不等考虑删除、修改、增加的情况dp[i][j] Math.min(dp[i-1][j],Math.min(dp[i-1][j-1], dp[i][j-1])) 1;}
3.dp数组初始化
同样的我们需要对dp数组的第一行和第一列进行初始化
dp[i][0]表示word1中以i-1结尾的子串要变成word2中空串需要的最小操作数只需要删除对应的字符即可故dp[i][0]i
dp[0][j]表示word1中空串要变成word2中以j-1结尾的子串需要的最小操作数只需要增加对应的字符即可故dp[0][j]j // 初始化dp数组for (int i 1; i word1.length(); i) {// word1以i-1个字符结尾的子序列变成空字符串需要删除的字符个数为idp[i][0] i;}for (int j 1; j word2.length(); j) {// word2以j-1个字符结尾的子序列变成空字符串需要删除的字符个数为jdp[0][j] j;}
4.确认遍历顺序
dp值只与左方左上方和上方dp值有关因此外层正序遍历word1内层正序遍历word2即可
5.举例推导dp数组
输入word1 horse, word2 ros为例dp矩阵状态图如下 整体代码
class Solution {public int minDistance(String word1, String word2) {int[][] dp new int[word1.length()1][word2.length()1];// 初始化dp数组for (int i 1; i word1.length(); i) {// word1以i-1个字符结尾的子序列变成空字符串需要删除的字符个数为idp[i][0] i;}for (int j 1; j word2.length(); j) {// word2以j-1个字符结尾的子序列变成空字符串需要删除的字符个数为jdp[0][j] j;}// 遍历for (int i 1; i word1.length(); i) {for (int j 1; j word2.length(); j) {if (word1.charAt(i-1) word2.charAt(j-1)) {// 字符相等不需要删除dp[i][j] dp[i-1][j-1];}else {// 字符不等考虑删除、修改、增加的情况dp[i][j] Math.min(dp[i-1][j],Math.min(dp[i-1][j-1], dp[i][j-1])) 1;}}}return dp[word1.length()][word2.length()];}
}
力扣647.回文子串
给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
解法一暴力破解
解题思路
通过两层循环遍历所有的子串然后内层增加一个回文串判断如果子串是回文串则计数加1
class Solution {public int countSubstrings(String s) {int res 0;for (int i 0; i s.length(); i){for (int j i; j s.length(); j) {if (isHuiWenString(s.substring(i, j1))) {res;}}}return res;}public boolean isHuiWenString(String s) {int left 0, right s.length()-1;while (left right) {if (s.charAt(left) ! s.charAt(right)) return false;left;right--;}return true;}
}
解法二动态规划
解题思路
如果字符串开头和结尾的两个字符相同那么该子串是否为回文串则看去掉这两个字符后的子串是否为回文串。
动规五部曲
1.dp数组定义和含义
定义二维boolean类型dp数组大小为字符串s的长度dp[i][j]表示字符串s下标为[i,j]ij的子串是否为回文串。
2.dp数组递推公式
如果字符i等于字符j则考虑子串[i1,j-1]即dp[i1][j-1]的布尔值另外由于i1需要不大于j-1因此我们需哟爱单独处理j和i的距离小于2的情况。当j-i小于2且i和j对应字符相等时有两种情况a和aa这两种都是回文串都需要统计。
因此当i和j对应的字符相等时dp[i][j]为true的情况有i-j2和dp[i1][j-1]true。 if(s.charAt(i) s.charAt(j)) {if (j - i 1) {// 子串长度小于等于1即a或aa的情况res;dp[i][j] true;}else if (dp[i1][j-1]) {// 子串长度大于1且i1到j-1的子串是回文串res;dp[i][j] true;}}
3.dp数组初始化
对于dp数组初始化所有值都为false保证在统计前未匹配上
4.确认遍历顺序
根据dp推导公式dp[i][j]收到dp[i1][j-1]的影响即dp数组左下方的影响因此行需要逆序遍历列需要正序遍历另外由于我们统计的时[i,j]的子串因此要保证i不大于j。因此外层逆序遍历i内层正序遍历jj初始化为ii可以等于j
在填充的时候保证只填充数组的右上部分 for (int i s.length()-1; i 0; i--) {for (int j i; j s.length(); j) {}}
5.举例推导dp数组
输入aaadp[i][j]状态如下 整体代码
class Solution {public int countSubstrings(String s) {boolean[][] dp new boolean[s.length()][s.length()];int res 0;for (int i s.length()-1; i 0; i--) {for (int j i; j s.length(); j) {if(s.charAt(i) s.charAt(j)) {if (j - i 1) {// 子串长度小于等于1即a或aa的情况res;dp[i][j] true;}else if (dp[i1][j-1]) {// 子串长度大于1且i1到j-1的子串是回文串res;dp[i][j] true;}}}}return res;}
} 力扣516.最长回文子序列
给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。
解题思路
动规五部曲
1.dp数组定义和含义
定义二维dp数组大小为字符串s长度dp[i][j]表示子串[i,j]ij的最长回文序列长度
2.dp数组递推公式
当字符i等于字符j时dp[i][j]受到去掉两个字符后的子串的影响即dp[i][j] dp[i1][j-1]2
当字符i不等于字符j时考虑去掉字符i或字符j后的子串的最长回文子序列长度即dp[i1][j]和dp[i][j-1]取两者的最大值故dp[i][j] max{dp[i1][j],dp[i][j-1]} if (s.charAt(i) s.charAt(j)) {// 字符相等去掉两个字符子串的回子序列长度2dp[i][j] dp[i1][j-1] 2;}else {// 字符不相等看去掉首尾字符得到的回文子序列哪个大dp[i][j] Math.max(dp[i1][j], dp[i][j-1]);}
3.dp数组初始化
对于单个字符的情况其初始值应该为1也可以后续进行初始化只要保证在使用到之前进行了初始化即可 // dp数组初始化单字符的情况也可以后续遍历时赋值for (int i 0; i s.length(); i) {dp[i][i] 1;}
4.确认遍历顺序
本题的dp值与左方、下方和左下方的dp值有关因此采用外层逆序遍历i内层正序遍历j的方式注意在内层如果之前初始化了dp[i][j]则j从i1开始处理否则从ji开始处理并对ij的情况进行单独赋值。 for (int i s.length()-1; i 0; i--) {for (int j i1; j s.length(); j) {}}
5.举例推导dp数组
s:cbbd 为例dp数组状态如图 整体代码
class Solution {public int longestPalindromeSubseq(String s) {int[][] dp new int[s.length()][s.length()];// dp数组初始化单字符的情况也可以后续遍历时赋值for (int i 0; i s.length(); i) {dp[i][i] 1;}for (int i s.length()-1; i 0; i--) {for (int j i1; j s.length(); j) {if (s.charAt(i) s.charAt(j)) {// 字符相等去掉两个字符子串的回子序列长度2dp[i][j] dp[i1][j-1] 2;}else {// 字符不相等看去掉首尾字符得到的回文子序列哪个大dp[i][j] Math.max(dp[i1][j], dp[i][j-1]);}}}return dp[0][s.length()-1];}
}
单调栈部分
力扣793.每日温度
给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
解法一暴力解法超时
一个简单的方法就是遍历每个元素然后遍历它右侧的所有温度找到第一个比它高的温度则记录下来反之则不记录。
class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] result new int[temperatures.length];for (int i 0; i temperatures.length; i) {// 遍历每一天for (int j i 1; j temperatures.length; j) {// 遍历后面的每一天找到第一个温度高的时候记录结果并跳出循环if (temperatures[j] temperatures[i]) {result[i] j-i;break;}}}return result;}
}
解法二单调栈
创建一个栈存储元素的下标保证栈中的元素从栈顶到栈顶是递增的即栈顶元素比它下面的元素大。
对于一个访问元素它和栈顶元素的关系有
当前元素比栈顶元素大则将栈顶元素出栈然后记录出栈元素的结果为result[st.peek()]i-st.pop()即栈顶元素的对应的结果为当前元素下标减去栈顶元素下标。注意这里要循环出栈直到栈为空或者栈顶元素大于当前元素。 while (!stack.isEmpty() temperatures[i] temperatures[stack.peek()]) {// 单调栈非空且访问元素大于栈顶元素时保持持续出栈int k stack.pop();// 栈顶元素下标result[k] i-k;// 记录结果}
当前元素小于等于栈顶元素或者栈为空时直接将元素下标入栈即可 // 当前元素不大于栈顶元素或栈空时当前元素下标入栈stack.push(i);
整体代码
class Solution {public int[] dailyTemperatures(int[] temperatures) {StackInteger stack new Stack();// 单调栈存储下标int[] result new int[temperatures.length];// 结果集stack.push(0);// 存入第一个元素下标for (int i 1; i temperatures.length; i){while (!stack.isEmpty() temperatures[i] temperatures[stack.peek()]) {// 单调栈非空且访问元素大于栈顶元素时保持持续出栈int k stack.pop();// 栈顶元素下标result[k] i-k;// 记录结果}// 当前元素不大于栈顶元素或栈空时当前元素下标入栈stack.push(i);}return result;}
}
力扣496.下一个更大的元素1
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 下标从 0 开始计数其中nums1 是 nums2 的子集。
对于每个 0 i nums1.length 找出满足 nums1[i] nums2[j] 的下标 j 并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案满足 ans[i] 是如上所述的 下一个更大元素 。
解法一暴力算法
解题思路
注意本题要找的是nums1的元素在nums2中对应位置后面的元素是否有下一个更大的元素不是在nums2中所有元素因此暴力算法的思路为
遍历nums1内部遍历nums2找到nums1元素对应在nums2中的下标位置然后从这个位置起遍历nums2的剩余元素找到下一个更大的元素。
整体代码
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int[] result new int[nums1.length];for (int i 0; i nums1.length; i) {// 遍历nums1的元素int left 0;for (int j 0; j nums2.length; j) {// 找nums2中的nums1[i]对应的元素if (nums1[i] nums2[j]){left j;break;}}result[i] -1;// 初始化// 找nums2中nums1[i]对应的元素后面的第一个比它大的元素left;while (left nums2.length) {if (nums2[left] nums1[i]) {// 找到第一个比nums1[i]大的元素记录结果并跳出循环result[i] nums2[left];break;}left;}}return result;}
}
解法二单调栈
解题思路
用一个Map存储nums1中元素和下标的映射用于后续找到对应元素在nums1中的下标值。
单调栈只用来存储nums2的元素下标也可以直接存储元素值当nums2中的元素大于栈顶元素时在map映射中找对应元素是否存在不存在则直接将栈顶元素出栈否则找到nums1对应元素的下标然后对结果进行赋值直到栈为空或者nums2当前元素不大于栈顶元素。
当nums2的当前元素小于等于栈顶元素时将元素入栈。
整体代码
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {MapInteger, Integer map new HashMap();// nums1元素和下标的映射int[] result new int[nums1.length];// 结果集只记录nums1即可Arrays.fill(result, -1);// 初始化为-1表示不存在存在则后续会覆盖for (int i 0; i nums1.length; i) {map.put(nums1[i], i);// 记录nums1元素和下标映射}StackInteger stack new Stack();// 单调栈记录nums2的元素下标stack.push(0);// 遍历nums2for (int i 1; i nums2.length; i) {if (nums2[i] nums2[stack.peek()]) {// 当前元素小于等于栈顶元素当前元素入栈stack.push(i);}else {// 当前元素大于栈顶元素栈顶元素出栈直到栈为空或者当前元素大于栈顶元素while (!stack.isEmpty() nums2[i] nums2[stack.peek()]) {int k stack.pop();// 栈顶元素出栈if (map.containsKey(nums2[k])) {// 判断nums2[k]对应的元素在nums1中是否存在int index map.get(nums2[k]);// nums2[k]对应的元素在nums1中的下标result[index] nums2[i];// 记录结果}}stack.push(i);}}return result;}
}
力扣503.下一个更大元素2
给定一个循环数组 nums nums[nums.length - 1] 的下一个元素是 nums[0] 返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序这个数字之后的第一个比它更大的数这意味着你应该循环地搜索它的下一个更大的数。如果不存在则输出 -1 。
解题思路
还是采用单调栈找右侧的第一个比它大的元素但这里与上一题不同的是需要对右侧未成功赋值的元素进行处理对数组进行循环他们的前方可能存在比它大的元素。
两次遍历数组
在第一次遍历数组完成后我们可以保证当元素右侧存在比它大的元素时它的结果能够被赋值此时右边没有更大值的元素还在单调栈中堆积着此时进行第二遍元素遍历。 // 第一遍遍历数组for (int i 1; i nums.length; i) {while (!stack.isEmpty() nums[i] nums[stack.peek()]) {int k stack.pop();result[k] nums[i];}stack.push(i);}
第二遍元素遍历能够找到元素左边是否有比它大的值当两次遍历完成后都没有对结果赋值的话表示它是最大值不需要赋值。 // 第二次遍历数组for (int i 0; i nums.length; i) {while (!stack.isEmpty() nums[i] nums[stack.peek()]) {int k stack.pop();result[k] nums[i];}stack.push(i);}
整体代码
class Solution {public int[] nextGreaterElements(int[] nums) {int[] result new int[nums.length];Arrays.fill(result, -1);StackInteger stack new Stack();stack.push(0);for (int i 1; i nums.length; i) {while (!stack.isEmpty() nums[i] nums[stack.peek()]) {int k stack.pop();result[k] nums[i];}stack.push(i);}for (int i 0; i nums.length; i) {while (!stack.isEmpty() nums[i] nums[stack.peek()]) {int k stack.pop();result[k] nums[i];}stack.push(i);}return result;}
}
上面的代码可以进一步简化直接for循环遍历2被数组大小然后下标对数组大小取模极为当前访问的元素下表能够保证访问元素两次完成元素赋值。
简化后的代码
class Solution {public int[] nextGreaterElements(int[] nums) {int[] result new int[nums.length];Arrays.fill(result, -1);StackInteger stack new Stack();stack.push(0);int n nums.length;for (int i 1; i 2*n; i) {while (!stack.isEmpty() nums[i%n] nums[stack.peek()]) {int k stack.pop();result[k] nums[i%n];}stack.push(i%n);}return result;}
}
力扣42.接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
解法一暴力破解超时
我们计算每一列能够存储的雨水数求和极为总雨水数。 对于某一列它的雨水数等于左右两侧比它本身柱子高的柱子中更矮的一个柱子与当前柱子之差
往左遍历找到左侧比当前柱子高的柱子往右遍历找到右侧比当前柱子高的柱子如果有一侧没有比当前柱子高的柱子那么说明当前柱子所在位置不存储雨水当左右两侧找到比当前柱子高的最大柱子时取两者间更矮的柱子高度当前柱子位置的雨水数更矮的柱子高度-当前柱子高度
可以理解为把左右两侧最高的柱子移到当前柱子两侧此时存储的雨水数极为当前柱子雨水数
整体代码
class Solution {public int trap(int[] height) {int result 0;// 总雨水量for (int i 1; i height.length-1; i) {// 遍历每一列从第二列开始到倒数第二列结束// 第一列没有左边柱子第二列没有右边柱子int left i-1, right i1;// 左右柱子下标int leftMaxHeight height[i], rightMaxHeight height[i];// 左右最高的柱子高度while (left 0) {// 找左边柱子比当前柱子更高的最高的柱子leftMaxHeight Math.max(leftMaxHeight, height[left]);left--;}while (right height.length) {// 找右边柱子比当前柱子更高的最高的柱子rightMaxHeight Math.max(rightMaxHeight, height[right]);right;}if (leftMaxHeight ! height[i] rightMaxHeight ! height[i]) {// 当前柱子两边都有比它高的柱子可以接雨水计算雨水量// 雨水量 当前柱子两边最高的柱子中更低的一个高度 - 当前柱子的高度result Math.min(leftMaxHeight, rightMaxHeight) - height[i];}// 当前柱子两边都没有比它高的柱子无法接雨水}return result;}
}
解法二双指针dp优化
在暴力解法中每一个格子的雨水数量为它左侧和右侧最大的柱子高度中的更小的一个与它本身的柱子高度差大于0但每次都是通过左右遍历去找到最大值每此都需要再次遍历数组有许多的重复步骤。
对上面的方法进行改进我们先将每个柱子左侧和右侧的最高柱子求出来保存到数组中后续只需要取对应的值即可。
这里左侧最高柱子为当前柱子高度和前一个格子的最高柱子高度两者的最大值前面可能没有比当前柱子更高的此时我们用本身高度代替防止后面出现负值此处就有dp的体现。 // 创建两个数组分别记录每个柱子左边和右边最高的柱子高度int[] leftMaxHeight new int[height.length];int[] rightMaxHeight new int[height.length];leftMaxHeight[0] height[0];for (int i 1; i height.length; i) {// 当前柱子左边最高的柱子高度为当前柱子高度和左边柱子当前最高高度中较大的一个leftMaxHeight[i] Math.max(leftMaxHeight[i-1], height[i]);}rightMaxHeight[height.length-1] height[height.length-1];for (int j height.length-2; j 0; j--) {// 当前柱子右边最高的柱子高度为当前柱子高度和右边柱子当前最高高度中较大的一个rightMaxHeight[j] Math.max(rightMaxHeight[j1], height[j]);}
后续遍历的时候只需要在两个数组中取对应值来使用即可 int result 0;for (int i 1; i height.length-1; i) {// 当前柱子两边最高的柱子中较低的一个高度减去当前柱子的高度就是当前柱子能接的雨水量result Math.min(leftMaxHeight[i], rightMaxHeight[i]) - height[i];}
整体代码
class Solution {public int trap(int[] height) {// 创建两个数组分别记录每个柱子左边和右边最高的柱子高度int[] leftMaxHeight new int[height.length];int[] rightMaxHeight new int[height.length];leftMaxHeight[0] height[0];for (int i 1; i height.length; i) {// 当前柱子左边最高的柱子高度为当前柱子高度和左边柱子当前最高高度中较大的一个leftMaxHeight[i] Math.max(leftMaxHeight[i-1], height[i]);}rightMaxHeight[height.length-1] height[height.length-1];for (int j height.length-2; j 0; j--) {// 当前柱子右边最高的柱子高度为当前柱子高度和右边柱子当前最高高度中较大的一个rightMaxHeight[j] Math.max(rightMaxHeight[j1], height[j]);}int result 0;for (int i 1; i height.length-1; i) {// 当前柱子两边最高的柱子中较低的一个高度减去当前柱子的高度就是当前柱子能接的雨水量result Math.min(leftMaxHeight[i], rightMaxHeight[i]) - height[i];}return result;}
}
解法三单调栈
单调栈的方式是按照行计算雨水数这很抽象简单的理解就是凹槽中的雨水量等于宽*高
其中高为左边柱子和右边柱子的最小值减去底的高度宽为右边柱子下标减去左边柱子下表-1 对于单调栈我们采用栈底到栈顶元素大小为从大到小的方式则对于元素与栈顶元素处理为
当前元素高度小于栈顶元素则直接将该元素下标入栈 if (!stack.isEmpty() height[i] height[stack.peek()]){// 当前元素高度小于栈顶元素直接入栈stack.push(i);}
当前元素高度等于栈顶元素此处处理和前面不一样我们需要将栈顶元素入栈然后将该元素下表入栈这里是因为元素高度相同时我们只需要保留右侧元素用于后续作为左侧柱子即可
else if (!stack.isEmpty() height[i] height[stack.peek()]){// 当前元素高度等于栈顶元素将栈顶元素出栈当前元素入栈stack.pop();stack.push(i);}
当前元素高度大于栈顶元素此时就是收集雨水的时候将栈顶元素出栈作为低的高度然后在栈非空的情况下再次出出栈元素作为左边的柱子根据这三个值计算收集的雨水量。注意这里同样需要进行循环处理直到当前元素高度不大于栈顶元素将当前元素下标入栈 else {while (!stack.isEmpty() height[i] height[stack.peek()]) {int bottom stack.pop();// 底柱子下标if (!stack.isEmpty()) {// 栈非空找左边的柱子int left stack.peek();// 高为当前柱子和左边柱子的最小值减去底的高度int h Math.min(height[left], height[i]) - height[bottom];// 宽为当前柱子下标减去左边柱子下标减一只有中间能用int w i-left-1;result h*w;// 雨水量为宽乘高}}// 栈为空或当前元素不大于栈顶元素了当前元素入栈stack.push(i);}
整体代码
class Solution {public int trap(int[] height) {StackInteger stack new Stack();// 单调栈存储柱子下标保证柱子从栈底到栈顶为从大到小int result 0;stack.push(0);for (int i 1; i height.length; i) {if (!stack.isEmpty() height[i] height[stack.peek()]){// 当前元素高度小于栈顶元素直接入栈stack.push(i);}else if (!stack.isEmpty() height[i] height[stack.peek()]){// 当前元素高度等于栈顶元素将栈顶元素出栈当前元素入栈stack.pop();stack.push(i);}else {while (!stack.isEmpty() height[i] height[stack.peek()]) {int bottom stack.pop();// 底柱子下标if (!stack.isEmpty()) {// 栈非空找左边的柱子int left stack.peek();// 高为当前柱子和左边柱子的最小值减去底的高度int h Math.min(height[left], height[i]) - height[bottom];// 宽为当前柱子下标减去左边柱子下标减一只有中间能用int w i-left-1;result h*w;// 雨水量为宽乘高}}// 栈为空或当前元素不大于栈顶元素了当前元素入栈stack.push(i);}}return result;}
} 力扣84.柱状图中最大的矩形
给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。
求在该柱状图中能够勾勒出来的矩形的最大面积。
解法一暴力解法超时
对于一个柱子它能带来的最大矩形的宽是固定的即为它的高度矩形的高度为它两侧的不低于它的柱子个数因此我们只需要找到它两侧第一个小于它高度的柱子这之间即为矩形高度。
因此对于第i个元素我们往左右两边遍历找到第一个高度小于它的柱子即可得到矩形的宽当前柱子能提供的最大矩形即为宽*高。
整体代码
class Solution {public int largestRectangleArea(int[] heights) {int result 0;for (int i 0; i heights.length; i) {int left i, right i;// 找左右小于当前高度柱子的下表// 左for (; left 0; left--) {// 找到了左边更矮的柱子if (heights[left] heights[i]) break;}// 右for (; right heights.length; right) {// 找到了右边更矮的柱子if (heights[right] heights[i]) break;}// 高度为当前高度宽为左右下标差值减一int w right - left -1;int h heights[i];result Math.max(result, w*h);}return result;}
}
解法二双指针改进暴力法
同样可以使用双指针对暴力法进行改进。
用两个数组分别存储第i个元素左边和后边第一个小于其高度的柱子标找不到则左边下标为-1右边下标为数组大小。
左边第一个矮的柱子数组
遍历整个数组然后用while循环往左找更小的柱子这里当t的高度小于i时则找到了结果否则的话由于i的高度不大于t则t的更小柱子下标到t之间的柱子的高度要比i大因此可以直接跳过 // 往左遍历leftMinIndex[0] -1;// 左边没有更小的for (int i 1; i heights.length; i) {int t i-1;// 往左寻找while (t 0 heights[t] heights[i]){t leftMinIndex[t];// 当前i柱子比t柱子还小则t的更小柱子到t之间的一定比i更高或者相等因此可以剪枝}leftMinIndex[i] t;// t为-1或t为左边第一个小于当前高度柱子的下标}
右边第一个矮的柱子数组和左侧数组是一样的 // 往右遍历rightMinIndex[heights.length-1] heights.length;// 右边没有更小的for (int j heights.length - 2; j 0; j--) {int t j1;// 往右边找while (t heights.length heights[t] heights[j]) {t rightMinIndex[t];// 当前j柱子比t柱子还小则t到t的更小柱子之间的一定比j更高或者相等因此可以剪枝}rightMinIndex[j] t;// t为heights.length或t为右边第一个小于当前高度柱子的下标}
整体代码
class Solution {public int largestRectangleArea(int[] heights) {int[] leftMinIndex new int[heights.length];// 每个位置左边第一个小于当前高度柱子的下标int[] rightMinIndex new int[heights.length];// 每个位置右边第一个小于当前高度柱子的下标// 往左遍历leftMinIndex[0] -1;// 左边没有更小的for (int i 1; i heights.length; i) {int t i-1;// 往左寻找while (t 0 heights[t] heights[i]){t leftMinIndex[t];// 当前i柱子比t柱子还小则t的更小柱子到t之间的一定比i更高或者相等因此可以剪枝}leftMinIndex[i] t;// t为-1或t为左边第一个小于当前高度柱子的下标}// 往右遍历rightMinIndex[heights.length-1] heights.length;// 右边没有更小的for (int j heights.length - 2; j 0; j--) {int t j1;// 往右边找while (t heights.length heights[t] heights[j]) {t rightMinIndex[t];// 当前j柱子比t柱子还小则t到t的更小柱子之间的一定比j更高或者相等因此可以剪枝}rightMinIndex[j] t;// t为heights.length或t为右边第一个小于当前高度柱子的下标}// 正式遍历寻找结果int result 0;for (int i 0; i heights.length; i) {int w rightMinIndex[i] - leftMinIndex[i] - 1;// 宽度int h heights[i];// 高度result Math.max(result, w*h);}return result;}
}
解法三单调栈
本题和42接雨水的思路很像接雨水是找一个柱子左右两侧第一个更大的柱子本题找的是左右两侧第一个更小的柱子找到两个这种柱子left和right后当前节点能得到的最大矩形为高*宽其中高为当前节点柱子的高宽为right-left-1。
本题的单调栈找的是第一个更小的因此单调栈内的元素保持栈底到栈顶元素递增的顺序。
第i个节点与栈顶元素的大小关系有三种
第i个元素高度大于栈顶元素此时直接将第i个元素下标入栈保证单调栈递增 if (!stack.isEmpty() heights[i] heights[stack.peek()]){// 当前元素高度大于栈顶元素直接入栈stack.push(i);}
第i个元素高度等于栈顶元素此时将栈顶元素出栈然后将第i个元素下标入栈 else if (!stack.isEmpty() heights[i] heights[stack.peek()]){ // 当前元素高度等于栈顶元素将栈顶元素出栈当前元素入栈stack.pop();stack.push(i);}
第i个元素高度小于栈顶元素此时就是进行计算结果的时候。当栈中存在元素时将栈顶元素cur出栈对此元素进行结果计算。当cur出栈后需要考虑栈是否为空当栈为空时表示左边没有更小的元素了此时的左边界下标为-1。当栈不为空时此时的栈顶元素即为cur的左边第一小的值i为右边第一个小的值从而计算第i个节点能够得到的最大矩形面积。 else {while (!stack.isEmpty() heights[i] heights[stack.peek()]){int cur stack.pop();if (!stack.isEmpty()) {int w i - stack.peek() - 1;int h heights[cur];result Math.max(result, w * h);}else {// 左边没有更小的柱子宽度为当前柱子下标左侧一个虚拟柱子下标为-1int w i;int h heights[cur];result Math.max(result, w * h);}}stack.push(i);}
注意本题要考虑最后一个元素的特殊情况最后一个元素可能是一直递增来的因此最后的递增序列没有计算。因此在遍历完数组后需要对栈中元素进行处理这里右边的边界用数组大小类似于虚拟一个高度为0的柱子用于作为右边第一个小的元素。即 // 处理最后一个元素的情况右边没有更小的柱子了设置右侧虚拟柱子下标为数组大小while (!stack.isEmpty()){int cur stack.pop();if (!stack.isEmpty()) {int w heights.length - stack.peek() - 1;int h heights[cur];result Math.max(result, w * h);}else {int w heights.length;int h heights[cur];result Math.max(result, w * h);}}
整体代码
class Solution {public int largestRectangleArea(int[] heights) {StackInteger stack new Stack();// 单调栈存储柱子下标保证柱子从栈底到栈顶为从小到大找左边的第一个更小值int result 0;stack.push(0);for (int i 1; i heights.length; i) {if (!stack.isEmpty() heights[i] heights[stack.peek()]){// 当前元素高度大于栈顶元素直接入栈stack.push(i);}else if (!stack.isEmpty() heights[i] heights[stack.peek()]){// 当前元素高度等于栈顶元素将栈顶元素出栈当前元素入栈stack.pop();stack.push(i);}else {while (!stack.isEmpty() heights[i] heights[stack.peek()]){int cur stack.pop();if (!stack.isEmpty()) {int w i - stack.peek() - 1;int h heights[cur];result Math.max(result, w * h);}else {// 左边没有更小的柱子宽度为当前柱子下标左侧一个虚拟柱子下标为-1int w i;int h heights[cur];result Math.max(result, w * h);}}stack.push(i);}}// 处理最后一个元素的情况右边没有更小的柱子了设置右侧虚拟柱子下标为数组大小while (!stack.isEmpty()){int cur stack.pop();if (!stack.isEmpty()) {int w heights.length - stack.peek() - 1;int h heights[cur];result Math.max(result, w * h);}else {int w heights.length;int h heights[cur];result Math.max(result, w * h);}}return result;}
}
