原始代码
我们枚举「高」，我们可以使用一重循环枚举某一根柱子，将其固定为矩形的高度 h。
随后我们从这跟柱子开始向两侧延伸，直到遇到高度小于 h 的柱子，就确定了矩形的左右边界。
如果左右边界之间的宽度为 w，那么对应的面积为 w * 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
;
}
};
单调栈
我们用一个具体的例子 [6, 7, 5, 2, 4, 5, 9, 3][6,7,5,2,4,5,9,3] 来帮助读者理解单调栈。
我们需要求出每一根柱子的左侧且最近的小于其高度的柱子。初始时的栈为空。
我们枚举 6，因为栈为空，所以 6 左侧的柱子是「哨兵」，位置为 -1。随后我们将 6 入栈。
栈：[6(0)]。（这里括号内的数字表示柱子在原数组中的位置）
我们枚举 5，由于 7≥5，因此移除栈顶元素 7。同样地，6≥5，再移除栈顶元素 6。此时栈为空，所以 5左侧的柱子是「哨兵」，位置为 -1。随后我们将 5 入栈。
栈：[5(2)]
这样以来，我们得到它们左侧的柱子编号分别为 [-1, 0, -1, -1, 3, 4, 5, 3]。用相同的方法，我们从右向左进行遍历，也可以得到它们右侧的柱子编号分别为 [2, 2, 3, 8, 7, 7, 7, 8]，这里我们将位置 8 看作「哨兵」。
class Solution {
public int largestRectangleArea(int[] heights
) {
int n
= heights
.length
;
int[] left
= new int[n
];
int[] right
= new int[n
];
Stack
<Integer> mono_stack
= new Stack<Integer>();
for (int i
= 0; i
< n
; ++i
) {
while (!mono_stack
.isEmpty() && heights
[mono_stack
.peek()] >= heights
[i
]) {
mono_stack
.pop();
}
left
[i
] = (mono_stack
.isEmpty() ? -1 : mono_stack
.peek());
mono_stack
.push(i
);
}
mono_stack
.clear();
for (int i
= n
- 1; i
>= 0; --i
) {
while (!mono_stack
.isEmpty() && heights
[mono_stack
.peek()] >= heights
[i
]) {
mono_stack
.pop();
}
right
[i
] = (mono_stack
.isEmpty() ? n
: mono_stack
.peek());
mono_stack
.push(i
);
}
int ans
= 0;
for (int i
= 0; i
< n
; ++i
) {
ans
= Math
.max(ans
, (right
[i
] - left
[i
] - 1) * heights
[i
]);
}
return ans
;
}
}
优化
在方法一中，我们首先从左往右对数组进行遍历，借助单调栈求出了每根柱子的左边界，随后从右往左对数组进行遍历，借助单调栈求出了每根柱子的右边界。那么我们是否可以只遍历一次就求出答案呢？
答案是可以的。在方法一中，我们在对位置 i 进行入栈操作时，确定了它的左边界。从直觉上来说，与之对应的我们在对位置 i 进行出栈操作时可以确定它的右边界！仔细想一想，这确实是对的。当位置 i 被弹出栈时，说明此时遍历到的位置 i0的高度小于等于height[i]，并且在 i0与 i 之间没有其他高度小于等于height[i] 的柱子。这是因为，如果在 i和 i0之间还有其它位置的高度小于等于height[i] 的，那么在遍历到那个位置的时候，i 应该已经被弹出栈了。所以位置i0 就是位置 i 的右边界。 等等，我们需要的是「一根柱子的左侧且最近的小于其高度的柱子」，但这里我们求的是小于等于，那么会造成什么影响呢？答案是：我们确实无法求出正确的右边界，但对最终的答案没有任何影响。这是因为在答案对应的矩形中，如果有若干个柱子的高度都等于矩形的高度，那么最右侧的那根柱子是可以求出正确的右边界的，而我们没有对求出左边界的算法进行任何改动，因此最终的答案还是可以从最右侧的与矩形高度相同的柱子求得的。读者可以仔细思考一下这一步。
在遍历结束后，栈中仍然有一些位置，这些位置对应的右边界就是位置为 n 的「哨兵」。我们可以将它们依次出栈并更新右边界，也可以在初始化右边界数组时就将所有的元素的值置为 n。
class Solution {
public int largestRectangleArea(int[] heights
) {
int n
= heights
.length
;
int[] left
= new int[n
];
int[] right
= new int[n
];
Arrays
.fill(right
, n
);
Stack
<Integer> mono_stack
= new Stack<Integer>();
for (int i
= 0; i
< n
; ++i
) {
while (!mono_stack
.isEmpty() && heights
[mono_stack
.peek()] >= heights
[i
]) {
right
[mono_stack
.peek()] = i
;
mono_stack
.pop();
}
left
[i
] = (mono_stack
.isEmpty() ? -1 : mono_stack
.peek());
mono_stack
.push(i
);
}
int ans
= 0;
for (int i
= 0; i
< n
; ++i
) {
ans
= Math
.max(ans
, (right
[i
] - left
[i
] - 1) * heights
[i
]);
}
return ans
;
}
}
