LeetCode 503 Next Greater Element II

Tag: 设计数据结构 LeetCode Posted on 2022-02-11 13:28:12 Edited on 2022-02-11 13:41:33 Views: 153

概述

https://leetcode.com/problems/next-greater-element-ii/

直接法

暴力方法依然是遍历,直到遇到自己。

实现过程中要注意,当 i 为 0 而 j 越界时我们会将其重置为 0,此后务必要手动验证一下循环继续条件,否则将导致死循环。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> ans(nums.size(), -1);
        for (int i = 0; i < nums.size(); i ++) {
            for (int j = i + 1; j != i; j ++) {
                if (j == nums.size()) j = 0;
                if (j == i) break;  // if you mannually change the value of j, you must mannually verify the condition
                if (nums[j] > nums[i]) {
                    ans[i] = nums[j];
                    break;
                }
            }
        }
        return ans;
    }
};

数组翻倍 + 单调栈

https://labuladong.gitee.io/algo/2/20/51/

用取余来模拟数组翻倍,同时利用后续值覆盖掉前一半不正确的值。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);
        stack<int> s;
        for (int i = 2 * n - 1; i >= 0; i --) {
            while (!s.empty() && s.top() <= nums[i % n]) {
                s.pop();
            }
            if (!s.empty()) {
                ans[i % n] = s.top();
            }
            s.push(nums[i % n]);
        }
        return ans;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/