1 每日温度
- 题目链接：739. 每日温度
1.1 题目描述
给定一个整数数组 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]
1.2 思路
/analysis_of_question_and_solving_thought_here/
完整代码如下：
Cpp
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> res(n, 0);
stack<int> stk;
for(int i = 0; i < n; ++i){
while(!stk.empty() && temperatures[i] > temperatures[stk.top()]){
res[stk.top()] = i - stk.top();
stk.pop();
}
stk.emplace(i);
}
return res;
}
};C
int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize){
int n = temperaturesSize, stk_top = 0;
int stack[n];
stack[stk_top++]= 0;
int *res = (int *)malloc(sizeof(int)*n);
memset(res, 0, sizeof(res));
*returnSize = n;
for(int i = 1; i < n; ++i){
while(stk_top>0 && temperatures[i] > temperatures[stack[stk_top-1]]){
res[stack[stk_top-1]] = i - stack[stk_top-1];
stk_top--;
}
stack[stk_top++] = i;
}
return res;
} 2 下一个更大元素 I
- 题目链接：496. 下一个更大元素 I
2.1 题目描述
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 。
2.2 思路
先将nums1存到map中，创建一个单调栈以获取下一个更大元素(单调递减)，然后遍历nums2, 当当前元素大于栈顶元素时，说明栈顶元素找到了其下一个更大元素，则查看栈顶元素是否存在于map中(即查看nums1中是否存在该元素)，若存在则将其更大元素插入到答案数组的对应位置上。
完整代码如下：
Cpp实现
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> um;
int n1= nums1.size(), n2 = nums2.size();
for(int i = 0; i < n1; ++i){
um[nums1[i]] = i;
}
vector<int> res(n1, -1);
stack<int> stk;
for(int i = 0; i < n2; ++i){
while(!stk.empty() && nums2[stk.top()] < nums2[i]){
if(um.count(nums2[stk.top()])){
res[um[nums2[stk.top()]]] = nums2[i];
}
stk.pop();
}
stk.push(i);
}
return res;
}
};C实现
typedef struct {
int key;
int index;
UT_hash_handle hh;
}HashMap;
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
int *ans = (int *)malloc(sizeof(int)*nums1Size);
memset(ans, -1, sizeof(int)*nums1Size);
HashMap *set = NULL;
for(int i = 0; i < nums1Size; i++){
HashMap *tmp = malloc(sizeof(HashMap));
tmp->key = nums1[i];
tmp->index = i;
HASH_ADD_INT(set, key, tmp);
}
int stack[1000], stk_top = 0;
stack[stk_top++] = 0;
for(int i = 1; i < nums2Size; i++){
while(stk_top != 0 && nums2[i] > nums2[stack[stk_top - 1]]){
HashMap *tmp;
HASH_FIND_INT(set, &nums2[stack[stk_top-1]], tmp);
if(tmp){
ans[tmp->index] = nums2[i];
}
stk_top--;
}
stack[stk_top++] = i;
}
*returnSize = nums1Size;
return ans;
} 3 下一个更大元素 II
- 题目链接：503. 下一个更大元素 II
3.1 题目描述
给定一个循环数组 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]
3.2 思路
其实就是上一题，没啥大区别。
完整代码如下：
Cpp实现
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n);
for(int i = 0; i < n; i++){
res[i] = -1;
}
stack<int> stk;
stk.push(0);
for(int i = 1; i <= 2*n; i++){
while(!stk.empty() && nums[i%n] > nums[stk.top()]){
res[stk.top()] = nums[i%n];
stk.pop();
}
stk.push(i%n);
}
return res;
}
};C实现
int* nextGreaterElements(int* nums, int numsSize, int* returnSize){
*returnSize = numsSize;
int stack[2*numsSize], stk_top = 0; //要遍历两次，栈的容量要两倍，以防止溢出
int *ans =(int *)malloc(sizeof(int)*numsSize);
memset(ans, -1, sizeof(int)*numsSize);
if(numsSize == 1) return ans;
stack[stk_top++] = 0;
for(int i = 1;i < 2*numsSize; i++){
while(stk_top != 0 && nums[i%numsSize] > nums[stack[stk_top - 1]]){
ans[stack[stk_top - 1]] = nums[i%numsSize];
stk_top--;
}
stack[stk_top++] = i%numsSize;
}
return ans;
} 4 接雨水
- 题目链接：42. 接雨水
4.1 题目描述
给定 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
4.2 思路
遍历整个数组，维护一个单调递减栈，当当前遍历到的元素不满足单调递减时，说明有位置可以装水，因而将当前位置的高记为rHeight（桶的右高度）、下标为r，然后栈顶元素记为mHeight（其实就是桶底）,然后将出栈后的栈顶元素记为lHeight、下标为l（桶的左高度），则当前的桶的容量即为：(min(rHeight, lHegiht)-mHeight)*(r-l-1).
完整代码如下：
Cpp实现
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
stack<int> stk;
int ans = 0;
stk.push(0);
for(int i = 0;i < n; ++i){
while(!stk.empty() && height[i] > height[stk.top()]){
int mHeight = height[stk.top()];
stk.pop();
if(stk.empty()){
break;
}
int lHeight = height[stk.top()];
ans += (min(lHeight, height[i]) - mHeight) * (i - stk.top() - 1);
}
stk.emplace(i);
}
return ans;
}
};C实现
int trap(int* height, int heightSize){
if(heightSize <= 1) return 0;
int ans = 0;
int stack[heightSize], stk_top = 0;
stack[stk_top++] = 0;
for(int i = 0; i < heightSize; i++){
if(height[i] < height[stack[stk_top - 1]]){
stack[stk_top++] = i;
}else if(height[i] == height[stack[stk_top - 1]]){
stack[stk_top-1] = i;
}else{
while(stk_top != 0 && height[i] > height[stack[stk_top - 1]]){
int mid = stack[stk_top - 1];
stk_top--;
if(stk_top != 0){
int left = stack[stk_top - 1];
ans += (i - left - 1)*(fmin(height[i], height[left]) - height[mid]);
}
}
stack[stk_top++] = i;
}
}
return ans;
} 5 柱状图中最大的矩形
- 题目链接：84. 柱状图中最大的矩形
5.1 题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例1:
输入: heights = [2,1,5,6,2,3]
输出: 10
解释: 最大的矩形为图中红色区域，面积为 10
示例2:
输入: heights = [2,4]
输出: 4
5.2 思路
思路类似上一题。遍历数组，维护一个单调递增栈。
完整代码如下：
Cpp实现
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> stk;
stk.push(0);
heights.insert(heights.begin(), 0);
heights.emplace_back(0);
int result = 0;
// 第一个元素已经入栈，从下标1开始
for(int i = 1; i < heights.size(); i++){
while(heights[i] < heights[stk.top()]){ // 注意是while
int h = heights[stk.top()];
stk.pop();
int w = i - stk.top() - 1;
result = max(result, w*h);
}
stk.push(i);
}
return result;
}
};C实现
int largestRectangleArea(int* heights, int heightsSize){
int stack[heightsSize+2];
int stack_top = 0;
stack[stack_top++] = -1;
int ans = INT_MIN;
for(int i = 0; i <= heightsSize; i++){
while(stack_top > 1 &&(i==heightsSize || heights[i] < heights[stack[stack_top-1]])){
int h = heights[stack[--stack_top]];
int l = stack[stack_top-1];
ans = fmax(ans, (i-l-1)*h);
}
stack[stack_top++] = i;
}
return ans;
}
