柱状图中最大的矩形(Largest Rectangle in Histogram)——单调栈经典题目

小灰灰 2023-02-14 02:04 8阅读 0赞

# 柱状图中最大的矩形 #

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。  
![在这里插入图片描述][format_png]  
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 `[2,1,5,6,2,3]`。  
![在这里插入图片描述][format_png 1]  
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。  
示例:

输入: [2,1,5,6,2,3]
    输出: 10

# 代码 #

## 暴力法 ##

固定矩形的高度为h，随后我们从这跟柱子开始向两侧延伸，**直到遇到高度小于 h 的柱子**，就确定了矩形的左右边界。

class Solution { 
    public:
        int largestRectangleArea(vector<int>& heights) { 
            int n = heights.size();
            int ans = 0;
            for (int mid = 0; mid < n; ++mid) { 
                // 枚举高
                int height = heights[mid];
                int left = mid, right = mid;
                // 确定左右边界
                while (left - 1 >= 0 && heights[left - 1] >= height) { 
                    --left;
                }
                while (right + 1 < n && heights[right + 1] >= height) { 
                    ++right;
                }
                // 计算面积
                ans = max(ans, (right - left + 1) * height);
            }
            return ans;
        }
    };

[来自LeetCode-Solution][LeetCode-Solution]

## 单调栈+哨兵 ##

class Solution { 
        public int largestRectangleArea(int[] heights) { 
            int len = heights.length;
            if (len == 0) { 
                return 0;
            }
    
            if (len == 1) { 
                return heights[0];
            }
    
            int res = 0;
    
            int[] newHeights = new int[len + 2];
            newHeights[0] = 0;
            System.arraycopy(heights, 0, newHeights, 1, len);
            newHeights[len + 1] = 0;
            len += 2;
            heights = newHeights;
    
            Deque<Integer> stack = new ArrayDeque<>(len);
            // 先放入哨兵，在循环里就不用做非空判断
            stack.addLast(0);
            
            for (int i = 1; i < len; i++) {     	
                while (heights[i] < heights[stack.peekLast()]) { 
                    int curHeight = heights[stack.pollLast()];
                    int curWidth = i - stack.peekLast() - 1;
                    res = Math.max(res, curHeight * curWidth);
                }
                stack.addLast(i);
            }
            return res;
        }
    }

# 单调栈的问题 #

以下列出了单调栈的问题，供大家参考。

<table> 
 <thead> 
  <tr> 
   <th>序号</th> 
   <th>题目</th> 
   <th>题解</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td><a href="https://leetcode-cn.com/problems/trapping-rain-water/" rel="nofollow">42. 接雨水（困难）</a></td> 
   <td><a href="https://leetcode-cn.com/problems/trapping-rain-water/solution/bao-li-jie-fa-yi-kong-jian-huan-shi-jian-zhi-zhen-/" rel="nofollow">暴力解法、优化、双指针、单调栈</a></td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td><a href="https://leetcode-cn.com/problems/daily-temperatures/" rel="nofollow">739. 每日温度（中等）</a></td> 
   <td><a href="https://leetcode-cn.com/problems/daily-temperatures/solution/bao-li-jie-fa-dan-diao-zhan-by-liweiwei1419/" rel="nofollow">暴力解法 + 单调栈</a></td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td><a href="https://leetcode-cn.com/problems/next-greater-element-i/" rel="nofollow">496. 下一个更大元素 I（简单）</a></td> 
   <td><a href="https://leetcode-cn.com/problems/next-greater-element-i/solution/bao-li-jie-fa-dan-diao-zhan-by-liweiwei1419-2/" rel="nofollow">暴力解法、单调栈</a></td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td><a href="https://leetcode-cn.com/problems/remove-duplicate-letters/" rel="nofollow">316. 去除重复字母（困难）</a></td> 
   <td><a href="https://leetcode-cn.com/problems/remove-duplicate-letters/solution/zhan-by-liweiwei1419/" rel="nofollow">栈 + 哨兵技巧（Java、C++、Python）</a></td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td><a href="https://leetcode-cn.com/problems/online-stock-span/" rel="nofollow">901. 股票价格跨度（中等）</a></td> 
   <td><a href="https://blog.csdn.net/lw_power/article/details/103957702" rel="nofollow">「力扣」第 901 题：股票价格跨度（单调栈）</a></td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td><a href="https://leetcode-cn.com/problems/remove-k-digits/" rel="nofollow">402. 移掉K位数字</a></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td><a href="https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/" rel="nofollow">581. 最短无序连续子数组</a></td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

# 参考资料 #

[参考liweiwei1419][liweiwei1419]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE4LzEwLzEyL2hpc3RvZ3JhbS5wbmc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE4LzEwLzEyL2hpc3RvZ3JhbV9hcmVhLnBuZw?x-oss-process=image/format,png
[LeetCode-Solution]: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/zhu-zhuang-tu-zhong-zui-da-de-ju-xing-by-leetcode-/
[liweiwei1419]: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/