网站建设背景,松江新城做网站,企业自建网站有哪些,德阳做网站的公司Problem: 84. 柱状图中最大的矩形 文章目录 思路复杂度Code 思路
#x1f468;#x1f3eb; 参考地址 复杂度
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)
Code
class Solution {public static int largestRectangleArea(int[] height){Stack 参考地址 复杂度
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)
Code
class Solution {public static int largestRectangleArea(int[] height){StackInteger stack new StackInteger();// 单调递增栈 存的是下标int n height.length;int[] h new int[n 2];//加两 哨兵节点因为是单调递增栈 所以 加最小值h[0] 0;//前哨兵System.arraycopy(height, 0, h, 1, n);//把 height 数组 从 0 开始 复制长度为 [1,n] (n-1 1)的长度到 h 数组h[n 1] 0;//后哨兵int m n 2;int ans 0;for (int i 0; i m; i){while (!stack.isEmpty() h[i] h[stack.peek()]){int cur stack.pop();//这是区间的最小值,现在 i 并没有入栈// 至此h(lr)开区间内都是 大于 h[cur]int l stack.peek() 1;// 当前栈顶为左边的第一个小于 h[cur] 的值 的下标ans Math.max(ans, (i - l) * h[cur]);}
// stack.push(i);stack.add(i);}return ans;}
}
