【C++编程能力提升】

一、503 下一个更大元素II

题目链接：503 下一个更大元素II

核心：与496 下一个更大元素类似，区别在于本题要求循环数组，即最后一个元素的右边第一个更大元素可以从数组起始元素开始寻找。
解决方案是在nums后插入一个nums，那么原nums的最后一个元素是现在nums的中间元素，可以继续往后寻找下一个更大元素，只不过记录下一个更大元素值的res数组要先定义为扩充后的nums数组大小，返回时需resize成原nums数组大小。

    vector<int> nextGreaterElements(vector<int>& nums) {
    //循环数组，可以在nums数组后增加一个nums，就能完成循环数组的遍历
    vector<int> nums1(nums.begin(),nums.end());
    nums.insert(nums.end(),nums1.begin(),nums1.end()); //将原来nums扩充到2个nums
    vector<int> res(nums.size(),-1); //记录更大元素值
    stack<int> stk; //递增栈
    stk.push(0); //先push第一个元素
    for(int i=1;i<nums.size();++i)
    {//遍历nums元素时，push入栈的是下标
        if(nums[i]<nums[stk.top()])
            stk.push(i);
        else if(nums[i]==nums[stk.top()])
            stk.push(i);
        else
        {
            while(!stk.empty() && nums[i]>nums[stk.top()])
            {
                res[stk.top()]=nums[i]; //记录的是更大元素的值，而不是距离或位置
                stk.pop();
            }
            stk.push(i);
        }
    }
    res.resize(nums.size()/2);  //将扩充后的res回到原来nums数组的大小
    return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

二、42 接雨水

题目链接：42 接雨水

核心：与503 下一个更大元素II类似，同样利用递增栈寻找右边下一个更大元素值，也可确定栈顶元素的左边更大元素值，根据两个较大元素值求面积，所有面积之和即为所接的雨水量。

    int trap(vector<int>& height) {
    //与求解下一个更大元素类似，也是根据左边较大元素值和右边更大元素值求解面积（蓝色区域）
    stack<int> stk; //递增栈，存储元素下标，元素值可由下标确定
    stk.push(0);  //先push第一个元素值
    int sum=0;  //统计雨水面积
    for(int i=1;i<height.size();++i)
    {
        if(height[i]<height[stk.top()])
            stk.push(i);
        else if(height[i]==height[stk.top()])
        {//遇到相等元素不再是直接入栈，而是先弹出栈顶再入栈，目的是更新栈顶元素
            stk.pop();  
            stk.push(i);
        }
        else
        {
            while(!stk.empty() && height[i]>height[stk.top()])
            {//当前元素大于栈顶元素时就得到一个凹槽，可以接雨水，需要计算面积
                int mid=stk.top();  //凹槽中间，实际接雨水的坐标
                stk.pop();  //弹出栈顶元素后的新栈顶元素实则为左边的较大元素值，即接雨水的左边界
                if(!stk.empty())
                {
                    int h=min(height[stk.top()],height[i])-height[mid];
                    int w=i-stk.top()-1; //凹槽右边界与左边界相减再减1，目的是只求中间宽度
                    sum+=h*w;  //一个凹糟的面积
                }
            }
            stk.push(i); //计算面积后依然要push当前元素下标，计算下一个更大元素值
        }
    }
    return sum;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32