84. 柱状图中最大的矩形
暴力解法虽然超时,但是仍然值得学习,因为这题的解法来源就是暴力优化。对于每一个值,找到其左边第一个小于其值得元素角标,右边第一个小于其值元素的角标,右角标减去左角标-1即为宽度,该值为高度,循环遍历比较得出最大矩形面积。但是因为每个柱都要找左右最近小于高度,有很多是重复计算,时间复杂度为O(N^2),必定不是最优解,有用例超时也正常。
//暴力解法 对于每一个值,找到其左边第一个低于它的和右边第一个低于它的,以他为高度的矩形最大值
int sum = 0;
for (int i = 0; i < heights.size(); i++) {
int left = i;
int right = i;
while (left >= 0) {
if (heights[left] < heights[i]) {
break;
}
left--;
}
while (right < heights.size()) {
if (heights[right] < heights[i]) {
break;
}
right++;
}
int w = right-left-1;
int h = heights[i];
sum = max(sum, w * h);
}
return sum;
如果说接雨水那道题很推荐用双指针的话,那么这道题根本不值得用,因为思路不再是单独计算每一列,而是直接变成长乘宽,前后有关联。且找到左边最近小于值和右边最近小于值时候还挺绕的,没有接雨水那么直白。而且还有左右边初始化,好难理解。思路和暴力很像,就是用数组存储节约了一些步骤,有点类似并查集的感觉。
// 双指针写法,怎么这个bi双指针也这么难写
int res = 0;
vector<int> leftMin(heights.size());
vector<int> rightMin(heights.size());
leftMin[0] = -1;
for (int i = 1; i < heights.size(); ++i) {
int t = i-1;
while (t >= 0 && heights[t] >= heights[i]) {
t = leftMin[t];
}
leftMin[i] = t;
}
rightMin[heights.size()-1] = heights.size();
for (int i = heights.size()-2; i >= 0; --i) {
int t = i+1;
while (t < heights.size() && heights[t] >= heights[i]) {
t = rightMin[t];
}
rightMin[i] = t;
}
for (int i = 0; i < heights.size(); ++i) {
int w = rightMin[i]-leftMin[i]-1;
int h = heights[i];
res = max(res, w*h);
}
return res;
强烈推荐单调栈,这些题坐下来,我甚至觉得单调栈都是模板题了。只要一个题目中要求右边最近大于,右边最近小于,或者遇到山峰、山谷的题目,就是单调栈(或者暴力贪心)。这题因为左右两个端点也可能包含在最大矩形的范围之内,因此前后各加一个零,(在卷积神经网络里这叫padding吧)。首角标直接入栈,这次是要求峰顶,因此是栈顶到栈底单调递减(如果是山谷如接雨水就是栈顶到栈底单调递增),分三种情况:当前大于,当前等于,当前小于,然后就是最后一种情况不满足单调了,不断出栈计算直至重新单调,原理类似双指针,但是更加巧妙也好理解。注意栈存储的是下角标而不是元素值。
// 单调栈写法
int res = 0;
stack<int> st;
// 头尾插入0元素,则头尾也可以参与矩形裁剪,这一点和接雨水不一样
heights.insert(heights.begin(), 0);
heights.push_back(0);
st.push(0);
// 第一个元素已经入栈,下标从1开始
for (int i = 1; i < heights.size(); i++) {
if (heights[i] > heights[st.top()]) {
st.push(i);
}
else if (heights[i] == heights[st.top()]) {
// 连续相等情况,可以只保留最新下标,while循环遍历时可以节省循环次数
st.pop();
st.push(i);
}
else {
while (!st.empty() && heights[i] < heights[st.top()]) {
int mid = st.top();
st.pop();
// 整体形成一个小山尖,然后峰顶作为高度,开始向前做计算,这里只要求最大值
if (!st.empty()) {
int left = st.top();
int right = i;
int w = right - left - 1;
int h = heights[mid];
res = max(res, w*h);
}
}
st.push(i);
}
}
return res;