网站建设可行性研究报告范文,三河市建设局网站,2024网站推广,东莞做网络推广的公司随想录日记part49 t i m e #xff1a; time#xff1a; time#xff1a; 2024.04.20 主要内容#xff1a;今天开始要学习单调栈的相关知识了#xff0c;今天的内容主要涉及#xff1a;柱状图中最大的矩形
84.柱状图中最大的矩形 Topic184.柱状图中最大的矩形
题目 time time 2024.04.20 主要内容今天开始要学习单调栈的相关知识了今天的内容主要涉及柱状图中最大的矩形
84.柱状图中最大的矩形 Topic184.柱状图中最大的矩形
题目
思路 代码实现如下
class Solution {public int largestRectangleArea(int[] heights) {// 双指针法int result 0;int len heights.length;int[] left new int[len];int[] right new int[len];left[0] -1;for (int i 1; i len; i) {int t i - 1;while (t 0 heights[t] heights[i])t left[t];left[i] t;}right[len - 1] len;for (int i len - 2; i 0; i--) {int t i 1;while (t len heights[t] heights[i])t right[t];right[i] t;}for (int i 0; i len; i) {int tem heights[i] * (right[i] - left[i] - 1);result Math.max(tem, result);}return result;}
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n) Topic2 接雨水 思路 与接雨水很像 class Solution {public int largestRectangleArea(int[] heights) {int result 0;int len heights.length;int[] newheights new int[len 2];newheights[0] 0;newheights[len 1] 0;for (int i 0; i len; i) {newheights[i 1] heights[i];}heights newheights;StackInteger stack new Stack();stack.push(0);for (int i 1; i len 2; i) {if (heights[i] heights[stack.peek()]) {stack.push(i);} else if (heights[i] heights[stack.peek()]) {stack.pop();stack.push(i);} else {while (!stack.isEmpty() heights[i] heights[stack.peek()]) {int mid stack.pop();if (!stack.isEmpty()) {int h heights[mid];int w i - stack.peek() - 1;result Math.max(h * w, result);}}stack.push(i);}}return result;}
}class Solution {public int trap(int[] height) {// 双指针法int result 0;int len height.length;for (int i 0; i len; i) {if (i 0 || i len - 1)continue;int lheight height[i];int rheight height[i];for (int l i - 1; l 0; l--) {lheight Math.max(lheight, height[l]);}for (int r i 1; r len; r) {rheight Math.max(rheight, height[r]);}int tem Math.min(rheight, lheight) - height[i];if (tem 0)result tem;}return result;}
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
