IT评测·应用市场-qidao123.com技术社区

标题: Leetcode 柱状图中最大的矩形 [打印本页]

---

作者: 农民    时间: 2024-10-20 16:28
标题: Leetcode 柱状图中最大的矩形

h 是右边界，连续多个高度递增的柱子，如果碰到下一个 h < 栈顶元素(是最大的元素，单调递增栈)，那么会不停出栈来更新计算最大面积。
并非是一次性计算出最大面积的，很紧张的一点是while (!stack.isEmpty()这一部分的判断条件，会持续多次计算并更新最大面积，
你提到的情况是非常紧张的，并且确着实某些情况下会让人觉得应该以栈底元素为高度，但现实上这必要从栈的完整处置惩罚流程来明确。我们仍然应该按照栈顶元素作为当前高度来计算矩形面积，而栈底元素终极也会被弹出并精确处置惩罚。
让我们详细分析这个详细输入 [5, 6, 7, 2] 的执行过程，看看为何终极仍会精确地处置惩罚到以栈底元素 5 为高度的矩形。
步调剖析：

初始化：

• 我们的输入数组是 [5, 6, 7, 2]，依然使用单调栈来计算最大矩形面积。
  
• 遍历每个柱子，同时维护一个递增栈（存放柱子的索引）。
  

遍历开始：

• i = 0, heights[0] = 5：
  
  
  
  • 栈为空，将 0 压入栈，栈为 [0]。
    
  
  
• i = 1, heights[1] = 6：
  
  
  
  • 栈顶元素对应的高度是 5，6 > 5，继承保持递增顺序，将 1 压入栈，栈为 [0, 1]。
    
  
  
• i = 2, heights[2] = 7：
  
  
  
  • 栈顶元素对应的高度是 6，7 > 6，继承递增，将 2 压入栈，栈为 [0, 1, 2]。
    
  
  
• i = 3, heights[3] = 2：
  
  
  
  • 如今，当前柱子 2 < 7，不再递增了，我们必要弹出栈顶来计算面积。
    
  
  

弹栈计算过程：

• 弹出 2 索引的柱子 (高度 7)：
  
  
  
  • 栈顶的高度是 7，宽度为 1（因为 i - stack.peek() - 1 = 3 - 1 - 1 = 1），即矩形面积为 7 * 1 = 7。
    
  • 更新最大面积为 7。
    
  
  
• 弹出 1 索引的柱子 (高度 6)：
  
  
  
  • 栈顶的高度是 6，宽度为 2（因为 i - stack.peek() - 1 = 3 - 0 - 1 = 2），即矩形面积为 6 * 2 = 12。
    
  • 更新最大面积为 12。
    
  
  
• 弹出 0 索引的柱子 (高度 5)：
  
  
  
  • 栈顶的高度是 5，宽度为 3（因为栈已为空，所以宽度就是 i = 3），即矩形面积为 5 * 3 = 15。
    
  • 更新最大面积为 15。
    
  
  

继承遍历：

• 压入当前柱子 2：
  
  
  
  • 如今将索引 3 压入栈，栈为 [3]。
    
  
  

遍历竣事：

• 遍历竣事后，栈中尚有元素 3，对应的高度是 2，我们必要处置惩罚剩余的栈：
  
  
  
  • 以高度 2 作为最后的矩形，高度为 2，宽度为 4（因为栈为空，宽度就是整个数组的长度 n = 4），即矩形面积为 2 * 4 = 8。
    
  
  

终极结果：

最大面积是 15，对应的就是以高度 5 的矩形。
总结：

• 在 [5, 6, 7, 2] 的案例中，当碰到比栈顶更小的 2 时，栈中的元素会依次被弹出，起首以 7 作为高度计算矩形面积，接着以 6，最后以 5。栈底元素 5 也会在这个过程中被精确地弹出，并计算出它作为高度的最大矩形面积，因此终极以栈底元素 5 为高度的矩形仍然会被精确计算。
  
• 之所以使用栈顶元素作为 height，是因为栈顶元素对应的柱子是当前必要被“封闭”的柱子，当前柱子限制了栈顶柱子的右边界，所以我们必要计算以它为高度的最大矩形。
  
• 栈底元素终极也会被弹出并处置惩罚，只不外它的处置惩罚顺序是等到它的右边界被确定之后才会弹出计算，确保不会遗漏任何大概形成的更大矩形。
  

java solution

1. class Solution {
2.     public int largestRectangleArea(int[] heights) {
3.         int n = heights.length;
4.         int maxArea = 0;
5.         //栈中存放的是柱子的下标,而不是高度值
6.         Stack<Integer> stack = new Stack<>();
7.         for(int i = 0; i <= n; ++i) {
8.             //h是当前柱子的高度,当i == n 时意味着到达了我们设置的最右边界
9.             int h = (i == n) ? 0 : heights[i];
10.             //stack中的下标对应的元素值是递增的,栈顶元素作为下标所对应的元素是之前连续递增高度的最大值,
11.             //而h小于栈顶元素下标对应高度值,意味着碰到了右边界,需要我们持续出栈来多次更新计算最大面积值
12.             while(!stack.isEmpty() && h < heights[stack.peek()]) {
13.                 //确定高度和宽度
14.                 int height = heights[stack.pop()];
15.                 int width = (stack.isEmpty()) ? i : i - stack.peek() - 1;
16.                 maxArea = Math.max(maxArea, height * width);
17.             }
18.             stack.push(i);
19.         }
20.         return maxArea;
21.     }
22. }

复制代码

关于宽度简直定

int width = stack.isEmpty() ? i : i - stack.peek() - 1;


这行代码是用于计算当前弹出的栈顶元素形成的矩形的 宽度。它看起来有点复杂，但着实逻辑很清楚：我们要确定以弹出柱子的高度为底子的矩形，它的左右边界分别是什么。
代码片段：

1. int width = stack.isEmpty() ? i : i - stack.peek() - 1;

复制代码

这行代码的作用是计算矩形的宽度，决定矩形的左右边界。我们可以将其分为两个部分来明确。
1. 为什么必要计算宽度？

当我们从栈中弹出一个柱子时，这个柱子的高度成为当前矩形的高度，但我们还必要知道矩形的左右边界才能计算面积。

• 右边界：当前柱子 i 的索引可以看作是右边界，因为当我们弹出栈顶元素时，当前遍历到的柱子高度 h 比栈顶柱子矮（h < heights[stack.peek()]），因此它限制了栈顶柱子的扩展。
  
• 左边界：左边界取决于栈中剩下的下一个元素（也就是当前弹出的柱子左边比它更低的柱子）。如果栈中已经没有元素了，说明弹出的这个柱子可以从索引 0 开始扩展到当前索引 i - 1。
  

2. 代码表明

1. int width = stack.isEmpty() ? i : i - stack.peek() - 1;

复制代码

这行代码是用来计算弹出的栈顶柱子对应的矩形宽度的，有两种情况：
情况 1：栈为空（stack.isEmpty()）

• 说明：当我们弹出栈顶元素后，栈为空，意味着弹出的柱子左边没有任何柱子拦阻它的扩展。因此，弹出的这个柱子可以从索引 0 一直延伸到当前柱子的索引 i - 1。
  
• 宽度：在这种情况下，矩形的宽度就是从 0 到 i - 1，即宽度为 i。所以 width = i。
  
• 举例：假设栈中只有一个柱子 heights[0] = 5，遍历到 i = 3，此时弹出栈顶，栈变为空，矩形宽度是 3，因为它可以从索引 0 扩展到索引 2，即 width = 3。
  

情况 2：栈不为空（!stack.isEmpty()）

• 说明：当弹出栈顶元素后，栈中尚有其他柱子，这意味着弹出的柱子左边有另一个较低的柱子拦阻它扩展。此时，弹出栈顶柱子的矩形的左边界由下一个栈顶元素（stack.peek()）决定。
  
• 宽度计算：矩形的宽度是从下一个栈顶元素的索引 stack.peek() 加 1，到当前柱子之前的索引 i - 1。因此，宽度为 i - stack.peek() - 1。
  
• 举例：假设栈中有两个柱子 heights[0] = 5 和 heights[1] = 6，遍历到 i = 3，此时弹出 heights[1]，栈中剩下 heights[0]。弹出 heights[1] 后，宽度是从 stack.peek() 位置（即 0）加 1 到当前索引 i - 1，即 3 - 0 - 1 = 2。
  

当栈不为空时，我们的目的是计算当前弹出栈顶元素所能形成的矩形宽度，它的左右边界分别是：

• 右边界：当前遍历到的柱子之前的索引，也就是 i - 1。
  
• 左边界：栈中下一个元素的索引 stack.peek()，这个元素是弹出栈顶元素左边的柱子，它限制了弹出柱子的扩展，所以左边界应是 stack.peek() + 1。
  

因此，宽度的计算可以表示为：

1. width = (i - 1) - (stack.peek() + 1) + 1

复制代码

简化后就是：

1. width = i - stack.peek() - 1

复制代码

这个公式简便地表达了矩形的宽度，涵盖了从左边界（stack.peek() 后的那一个柱子）到右边界（当前柱子的前一个位置）的距离。
你已经把握了宽度计算的关键逻辑，非常棒！
3. 详细示例

我们用 [5, 6, 7, 2] 这个例子来展示如何计算宽度。

• 初始状态：遍历 5, 6, 7 时，栈依次存入 [0, 1, 2]。
  
• 碰到 2 时：2 < 7，开始弹出栈顶元素。
  
  
  
  • 弹出 7（索引 2）：
    
    
    
    • 栈中剩下 [0, 1]，7 的右边界是当前索引 3，左边界是 6 的位置（stack.peek() 为 1）。
      
    • 宽度为 3 - 1 - 1 = 1，矩形面积为 7 * 1 = 7。
      
    
    
  • 弹出 6（索引 1）：
    
    
    
    • 栈中剩下 [0]，6 的右边界仍然是当前索引 3，左边界是 5 的位置（stack.peek() 为 0）。
      
    • 宽度为 3 - 0 - 1 = 2，矩形面积为 6 * 2 = 12。
      
    
    
  • 弹出 5（索引 0）：
    
    
    
    • 栈为空，所以 5 的右边界是当前索引 3，而左边界是 0。
      
    • 宽度为 3（因为栈为空），矩形面积为 5 * 3 = 15。
      
    
    
  
  

4. 总结

• 宽度的计算逻辑：
  
  
  
  • 如果栈为空，说明弹出的柱子可以扩展到最左端，即从 0 到当前索引的前一个位置，宽度为 i。
    
  • 如果栈不为空，说明弹出的柱子左边有其他柱子拦阻，它的左边界由下一个栈顶元素的索引决定，宽度为 i - stack.peek() - 1。
    
  
  

通过这行代码，我们可以准确地计算每个弹出栈顶柱子所能形成的最大矩形的宽度，并团结高度一起更新矩形面积。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4