本文主要是介绍Day60 单调栈 part03,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Day60 单调栈 part03
最后一天啦!完结撒花~
84.柱状图中最大的矩形
我的思路:
感觉和接雨水差不多,只需要多考虑一些情况
双指针
lheight 和 rheight 分别是用来存储每个柱子的左边界和右边界的数组。
解答:
class Solution {public int largestRectangleArea(int[] heights) {int res = 0;int[] lheigth = new int[heights.length];int[] rheight = new int[heights.length];for(int i = 0; i < heights.length; i++) {int j = i - 1;while(j >= 0 && heights[j] >= heights[i]) {j = lheigth[j];}lheigth[i] = j;}for(int i = heights.length - 1; i >= 0; i--) {int j = i + 1;while(j < heights.length && heights[j] >= heights[i]) {j = rheight[j];}rheight[i] = j;}for(int i = 0; i < heights.length; i++) {int h = heights[i];int w = rheight[i] - lheigth[i] - 1;res = Math.max(res, h * w);}return res;}
}
单调栈
解答:
class Solution {public int largestRectangleArea(int[] heights) {Stack<Integer> stack = new Stack<>();int res = 0;int n = heights.length;for(int i = 0; i <= n; i++) {int currheight = (i == n) ? 0 : heights[i];while(!stack.isEmpty() && currheight < heights[stack.peek()]) {int h = heights[stack.pop()];int distance = stack.isEmpty() ? i : i - stack.peek() - 1;res = Math.max(res, distance * h);}stack.push(i);}return res;}
}
革命尚未成功,同志仍需努力!
这篇关于Day60 单调栈 part03的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!