给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90] 输出: [1,1,0]
思路：
首先想到的当然是暴力解法，两层for循环，把至少需要等待的天数就搜出来了。时间复杂度是O(n^2)。
那么接下来在来看看使用单调栈的解法。
什么时候用单调栈呢？
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。
就是用一个栈来记录我们遍历过的元素，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。
单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。
使用单调栈主要有三个判断条件。
- 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
也就是说，这道题就是小于等于时放入栈中，大于时弹出并写入result数组。
代码如下：
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int> st;
vector<int> result(temperatures.size(), 0);
st.push(0);
for (int i = 1; i < temperatures.size(); i++) {
if (temperatures[i] <= temperatures[st.top()]) {
st.push(i);
} else {
while (!st.empty() &&
temperatures[i] > temperatures[st.top()]) {
result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
}
return result;
}
};
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
示例 1：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出：[-1,3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。 - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。 - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4]. 输出：[3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。 - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
思路：
题目说如果不存在对应位置就输出 -1 ，所以result数组如果某位置没有被赋值，那么就应该是是-1，所以就初始化为-1。
在遍历nums2的过程中，我们要判断nums2[i]是否在nums1中出现过，因为最后是要根据nums1元素的下标来更新result数组。
注意题目中说是两个没有重复元素 的数组 nums1 和 nums2。
没有重复元素，我们就可以用map来做映射了。根据数值快速找到下标，还可以判断nums2[i]是否在nums1中出现过。
有关C++的map，set->
代码如下：
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int> res(nums1.size(), -1);
stack<int> st;
if (nums1.size() == 0)
return res;
unordered_map<int, int> nummap;
for (int i = 0; i < nums1.size(); i++) {
nummap[nums1[i]] = i;
}
st.push(0);
for (int i = 1; i < nums2.size(); i++) {
if (nums2[i] <= nums2[st.top()]) {
st.push(i);
} else {
while (!st.empty() && nums2[i] > nums2[st.top()]) {
if (nummap.count(nums2[st.top()]) > 0) { // 看是否存在
int index = nummap[nums2[st.top()]];
res[index] = nums2[i];
}
st.pop();
}
st.push(i);
}
}
return res;
}
};
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
输入: nums = [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2； 数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
示例 2:
输入: nums = [1,2,3,4,3] 输出: [2,3,4,-1,4]
和上题不同就是要处理两次数组。
方法就是i%num.size()
代码如下：
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> res(nums.size(), -1);
stack<int> st;
st.push(0);
if (nums.size() == 0)
return res;
for (int i = 1; i < nums.size() * 2; i++) {
if (nums[i % nums.size()] <= nums[st.top()]) {
st.push(i % nums.size());
} else {
while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
res[st.top()] = nums[i % nums.size()];
st.pop();
}
st.push(i % nums.size());
}
}
return res;
}
};
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5] 输出：9
思路：
用单调递减栈来实现。
雨水高度是 min(凹槽左边高度, 凹槽右边高度) – 凹槽底部高度，代码为：int h = min(height[st.top()], height[i]) - height[lowest];
雨水的宽度是 凹槽右边的下标 – 凹槽左边的下标 – 1（因为只求中间宽度），代码为：int w = i - st.top() - 1 ;
当前凹槽雨水的体积就是：h * w。
代码如下：
class Solution {
public:
int trap(vector<int>& height) {
// 单调递减栈
int res = 0;
stack<int> st;
st.push(0);
for (int i = 1; i < height.size(); i++) {
if (height[i] <= height[st.top()]) {
st.push(i);
} else {
while (!st.empty() && height[i] > height[st.top()]) {
int lowest = st.top();
st.pop();
if (!st.empty()) {
res += (min(height[st.top()], height[i]) -
height[lowest]) *
(i - st.top() - 1); // 高度*宽度
}
}
st.push(i);
}
}
return res;
}
};
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
思路：
和接雨水是相反的。
但要在头尾加上0，以满足只有两个元素的情况。
代码如下：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
// 单调递增栈
int res = 0;
stack<int> st;
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);
for (int i = 1; i < heights.size(); i++) {
if (heights[i] >= heights[st.top()]) {
st.push(i);
} else {
while (!st.empty() && heights[i] < heights[st.top()]) {
int highest = st.top();
st.pop();
res = max(res, highest);
if (!st.empty()) {
int h = heights[highest];
int w = i - st.top() - 1;
res = max(res, h * w);
}
}
st.push(i);
}
}
return res;
}
};
暂无评论