casyup.me@outlook.com

0%

leetcode/NextGreaterElementII

Posted on

Next Greater Element II

数组找最大值

my solution

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
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        nums.reserve(nums.size() * 2);
        back_insert_iterator<vector<int>> bi (nums);
        copy(nums.begin(), nums.end(), bi);

        stack<int> stk;
        int cnt = 0;
        while (cnt < nums.size()) {
            while (!stk.empty() && nums[stk.top()] < nums[cnt]) {
                nums[stk.top()] = nums[cnt];
                stk.pop();
            }

            if (cnt < nums.size() / 2)
                stk.push(cnt);
            cnt++;
        }

        while (!stk.empty()) {
            nums[stk.top()] = -1;
            stk.pop();
        }

        nums.resize(nums.size() / 2);
        return nums;
    }
};

用两个拼接的数组来解决循环的问题, 下一个最大数字分为两种情况

  1. 下一个数字比现在的数字大, 那么就可以直接替换当前数字, 并且在栈中继续这个过程
  2. 下一个数字小于等于当前数字, 入栈, 继续下次循环

当遍历到最后时, 有下一个最大数字的数字已经被填充了, 栈中剩余的数字即未找到下一个最大数字的数字

这个算法需要一倍额外的空间, 以及一个栈. 额外空间主要是因为数字会改变, 但是被改变的数字可能是其他数字所需要的数字. 暂时没有想到其他的方法. 而栈是用作记录, 在极端情况下 { 3, 2, 1…} 它等同于一倍的额外空间.

时间上, 是一个 O(n) 的算法. (平均情况比 n 大一些)

加上 ‘fast IO’ 的话还算个不错的结果, 我非常好奇有没有不用额外空间的算法.

the best solution

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
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> next_greater(n);
        if(n==0) return next_greater;

        int maxi=0;
        for(int i=0; i<n; i++) maxi = nums[i] > nums[maxi]? i:maxi;

        next_greater[maxi] = - 1;
        int p;
        for(int i=(maxi-1+n)%n; i!=maxi; i=(i-1+n)%n){
            p = (i+1)%n;
            while(p != -1 && nums[i] >= nums[p]) p = next_greater[p];
            next_greater[i] = p;
        }

        for(int i=0; i<n; i++){
            p = next_greater[i];
            next_greater[i] = p == -1? p: nums[next_greater[i]];
        }

        return next_greater;
    }
};

emmm… 我怎么感觉这个算法很邋遢…

从一开始的一次完整循环找最大值, 但是循环中不做其他事情(其实是可以想办法做一些能提高效率事情的, 一个完整的循环只用来找最大值, 太浪费了) . 循环问题它用取余来避免, 这是意料之中的. 也用了额外一倍的空间, 循环有三个, 两次肉眼可见完整的循环. 感觉并没有其他最优算法一样, 给人眼前一亮的感觉 = =.

The first cycle of this algorithm just find the max without anything can help efficiency. It used the same extra space and two complete cycles. It doesn’t feel as good as the other best algorithms.