文章目錄

• 題目描述
• 思路 && 代碼
• • • 二刷

題目描述

• 和接雨水有點(diǎn)像，但是具體做法還是有點(diǎn)不同。
  

思路 && 代碼

暴力法只能過 94 / 96 的樣例：復(fù)雜度O(n^2) & O(1)，一個(gè)雙重循環(huán)遍歷所有可行矩陣。
這里就直接用 O(n) & O(n)的做法了（空間換時(shí)間！）

• 思路：參考了Ikaruga的題解，循環(huán)找出以某列為高的最大矩陣，再對比這些矩陣大小。
• 時(shí)間復(fù)雜度：O(n)，最多對所有元素 存儲(chǔ)一次 + 計(jì)算一次。
• 計(jì)算值：以當(dāng)前列為最高列，可行的最大矩陣（ 也就代表該矩陣【左邊界，右邊界】的列，都大于或等于當(dāng)前列）
• 邊界處理：數(shù)組前、后添加一個(gè)0，保證不會(huì)漏算
  （比如恒遞增情況，不添0的話直接不計(jì)算了）

class Solution {public int largestRectangleArea(int[] heights) {int res = 0;// 單調(diào)棧：存儲(chǔ) indexDeque<Integer> stack = new ArrayDeque<>();// 前后添加0：處理邊界，讓heights[0], heights[len - 1] 都可以參與比較（參考恒遞增情況）int[] newHeights = new int[heights.length + 2];for(int i = 1; i < heights.length + 1; i++) {newHeights[i] = heights[i - 1];}// O(n)：遍歷新數(shù)組for(int i = 0; i < newHeights.length; i++) {// 棧不為空，且當(dāng)前棧頂更大（出現(xiàn)遞減情況）時(shí)while(!stack.isEmpty() && newHeights[stack.peek()] > newHeights[i]) {int index = stack.pop(); // 用于獲取當(dāng)前高int l = stack.peek(); // 獲取左邊第一個(gè)比當(dāng)前列矮的下標(biāo)int r = i; // 右邊第一個(gè)比當(dāng)前列矮的下標(biāo)// 計(jì)算：以stack.pop()為高，可行的最大矩形res = Math.max(res, (r - l - 1) * newHeights[index]);}// 加入當(dāng)前下標(biāo)（此時(shí)保持遞增）stack.push(i);}return res;} }

• 無注釋版

class Solution {public int largestRectangleArea(int[] heights) {int res = 0;Deque<Integer> stack = new ArrayDeque<>();int[] newHeights = new int[heights.length + 2];for(int i = 1; i < heights.length + 1; i++) {newHeights[i] = heights[i - 1];}for(int i = 0; i < newHeights.length; i++) {while(!stack.isEmpty() && newHeights[stack.peek()] > newHeights[i]) {int index = stack.pop();int l = stack.peek();int r = i;res = Math.max(res, (r - l - 1) * newHeights[index]);}stack.push(i);}return res;} }

二刷

• 單調(diào)棧，只能說 Dalao 思路還是強(qiáng)

class Solution {public int largestRectangleArea(int[] heights) {int[] newHeights = new int[heights.length + 2];for(int i = 1; i <= heights.length; i++) {newHeights[i] = heights[i - 1];}Deque<Integer> stack = new ArrayDeque<>();int max = 0;for(int i = 0; i < newHeights.length; i++) {// 當(dāng)前棧頂為最高列的可行值while(!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {int now = stack.poll();int left = stack.peek(); // 左邊第一個(gè)比 now 對應(yīng)值小的下標(biāo)int right = i; // 當(dāng)前即是右邊第一個(gè)比 now 對應(yīng)值小的下標(biāo)max = Math.max(max, (right - left - 1) * newHeights[now]); // 維護(hù) max}// 棧中比當(dāng)前大的都去掉了，now 可以加入棧，并保持單調(diào)增了。stack.push(i);}return max;} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】84. 柱状图中最大的矩形（字符串、单调栈）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。