503. 下一个更大元素 II
这题在最大温度的基础上加了一个循环数组的因素,但是最多遍历两遍,且最大值的元素没有后继较大值。有两种方法,一种是将题目给的数组复制两遍,拼接在一起,即可循环两次;另一种是所有的遍历完成之后,再对原数组进行一次遍历,即可将栈中未找到后继更大元素的位置填满。再复习一遍,找到右边最近的较大元素从左到右遍历,栈顶到栈底单调递增;找到左边最大元素,从右向做遍历,栈顶到栈底递增;找到右边最近的较小元素,从左往右遍历,栈顶到栈底递减。
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> res(nums.size(), -1);
stack<int> st;
st.push(0);
for (int i = 1; i < nums.size(); i = ++i) {
if (nums[i] <= nums[st.top()]) {
st.push(i);
}
else {
while (!st.empty() && nums[i] > nums[st.top()]) {
res[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
}
// 栈中只有一个元素即最大值时不可以再找了
if (st.size() != 1) {
// 再来遍历一遍确保所有都找到了后一个较大值
for (int i = 0; i < nums.size(); i = ++i) {
if (nums[i] <= nums[st.top()]) {
st.push(i);
}
else {
while (!st.empty() && nums[i] > nums[st.top()]) {
res[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
}
}
return res;
}
};
42. 接雨水
暴力解法,即对于每一列,找到该列左边最大值和右边最大值,取左右最大值的较小值减去当前高度即为该列可以乘下的水量。
但要注意min(lheight, rheight) - height[i];是否大于零,否则会出现错误。
// 暴力解,对于每一个列,找出其左边的最大值和右边的最大值
int sum = 0;
for (int i = 0; i < height.size(); i++) {
if (i == 0 || i == height.size()-1) continue;
int lheight = height[i];
int rheight = height[i];
for (int j = i-1; j >= 0; j--) {
if (height[j] > lheight) {
lheight = height[j];
}
}
for (int j = i+1; j < height.size(); j++) {
if (height[j] > rheight) {
rheight = height[j];
}
}
int h = min(lheight, rheight) - height[i];
if (h > 0) sum += h;
}
return sum;
双指针解法,和暴力解一样的思路,即找到每个列左边最大值和右边最大值,取较小值减去当前值(大于零时有效),之前的暴力解法超时了,原因在于重复计算了每个列左右两边的最大值。可以采用两个数组leftMax和rightMax来存储当前i的左右两边的最大值分别为多少。递推公式为:
leftMax[i] = max(leftMax[i-1], height[i]);
rightMax[i] = max(rightMax[i+1], height[i]);
这样就是在O(n)时间内找到左右最大值。其与方法和暴力一样。
// 双指针解法
if (height.size() <= 2) return 0;
vector<int> leftMax(height.size(), 0);
vector<int> rightMax(height.size(), 0);
int size = height.size();
leftMax[0] = height[0];
// 从左往右遍历,找到当前值左边的最大值(包含本身)
for (int i = 1; i < height.size(); i++) {
leftMax[i]= max(leftMax[i-1], height[i]);
}
rightMax[size-1] = height[size-1];
// 从右向左遍历,找到当前值右边的最大值(包含本身)
for (int i = size-2; i >=0; i--) {
rightMax[i] = max(rightMax[i+1], height[i]);
}
int sum = 0;
for (int i = 0; i < size; i++) {
// 对于每一列,其左边的最大值和右边最大值的较小值减去当前列的高度值
int count = min(leftMax[i], rightMax[i]) - height[i];
// 若相减结果大于零是可以容纳水的加入结果和
if (count > 0) sum += count;
}
return sum;
单调栈解法,和之前的单调栈基本一样,首先就是栈内存储的是元素角标,栈顶到栈底单调递增;然后0角标直接入栈,对于当前元素和栈顶元素进行比较,当前小于栈顶,则直接入栈(保持单调递增);当前等于栈顶,栈顶出栈,当前入栈,保持高度连续值得最后一个元素角标;当前大于栈顶(不单调了),一直栈顶出栈直至小于等于当前值,期间进行积水计算,即三个值,mid是栈顶角标,left是次栈顶角标,right是当前值,计算积水量需要横向计算即矩形的体积长乘宽,
int h = min(height[i], height[st.top()]) - height[mid];
int w = i - st.top() - 1;
则高度sum += wh,此时由于单调栈的因素,不会出现wh为负数的情况,可以放心相加。
// 单调栈解法 : 栈顶到栈底从小到大
if (height.size() <= 2) return 0;
stack<int> st;
st.push(0);
int sum = 0;
for (int i = 1; i < height.size(); i++) {
// 分三种情况讨论,如果当前高度小于栈顶高度,直接入栈
if (height[i] < height[st.top()]) {
st.push(i);
}
//如果当前高度等于栈顶高度,更新栈顶角标,即保留高度连续相同的最后一个角标
else if (height[i] == height[st.top()]) {
st.pop();
st.push(i);
}
else {
// 当前高度大于栈顶角标高度,形成凹槽,开始积水
// 此时计算的积水即当前元素height【i】作为右边界,栈顶元素作为最低点,出栈后的下一个
// 栈顶元素作为左边界(相同的元素已经在前面出栈了),计算一个凹槽的积水量,当然,这个
// 计算不只是对一列,而是对从低到高的一个矩形进行计算
while (!st.empty() && height[i] > height[st.top()]) {
int mid = st.top();
st.pop();
if (!st.empty()) {
int h = min(height[i], height[st.top()]) - height[mid];
int w = i - st.top() - 1;
sum += w * h;
}
}
// 所有小于等于元素
st.push(i);
}
}
return sum;