算法
单调栈
时间复杂度: O(n)
空间复杂度: O(n)
C++代码
class Solution {
public:
static int largestRectangleArea(const vector<int> &heights) {
const int n = static_cast<int>(heights.size());
if (n == 0) {
return 0;
}
typedef stack<int, vector<int>> Stack;
Stack stk;
vector<int> left(n);
vector<int> right(n);
for (int i = 0; i < n; ++i) {
for (; !stk.empty() && heights[stk.top()] >= heights[i]; stk.pop()) {
}
left[i] = stk.empty() ? -1 : stk.top();
stk.push(i);
}
stk = move(Stack());
for (int i = n - 1; i >= 0; --i) {
for (; !stk.empty() && heights[stk.top()] >= heights[i]; stk.pop()) {
}
right[i] = stk.empty() ? n : stk.top();
stk.push(i);
}
int res = 0;
for (int i = 0; i < n; ++i) {
res = max(res, heights[i] * (right[i] - left[i] - 1));
}
return res;
}
};
Java代码
未完待续
Python3代码
未完待续
Go代码
func largestRectangleArea(heights []int) int {
var n int = len(heights)
if n == 0 {
return 0
}
var stk []int = []int{}
var left []int = make([]int, n)
var right []int = make([]int, n)
for i := 0; i < n; i++ {
for len(stk) > 0 && heights[stk[len(stk)-1]] >= heights[i] {
stk = stk[:len(stk)-1]
}
if len(stk) == 0 {
left[i] = -1
} else {
left[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
stk = stk[0:0]
for i := n - 1; i >= 0; i-- {
for len(stk) > 0 && heights[stk[len(stk)-1]] >= heights[i] {
stk = stk[:len(stk)-1]
}
if len(stk) == 0 {
right[i] = n
} else {
right[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
var res int = 0
for i := 0; i < n; i++ {
var rect int = heights[i] * (right[i] - left[i] - 1)
if (res < rect) {
res = rect
}
}
return res
}