Javaで単調スタックを使用する方法

1. 次に大きな要素

問題の説明

アイデアの詳細な説明

この質問では、より暴力的なものを選択してください。解決 。

まず結果を保存するために nums と同じ長さの res 配列を初期化し、nums の値を取り出し、nums2[j] == nums が見つかるまで nums2 を検索します。 [i]. 次に、nums2 の j からトラバースして、nums[i] より大きい配列を見つけて返します。見つからない場合は、-1.

コードと結果

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1;
        }
        return res;
    }
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        for(int i = 0 ; i < temperatures.length ; i++){
            int res = 0;
            for(int j = i+1 ; j < temperatures.length; j++){
                res++;
                if(temperatures[j] > temperatures[i]){
                    answer[i] = res;
                    break;
                } 
            }
        }
        return answer;
    }
}

ログイン後にコピー

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        Arrays.fill(ret, -1);
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < n * 2 - 1; i++) {//最多循环一次，只需要2*n-1就够用了
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                ret[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);//利用取模来进行循环也是一种常用的方法
        }
        return ret;
    }
}

ログイン後にコピー

以上がJavaで単調スタックを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。