Bagaimana untuk menggunakan timbunan monoton di Jawa

1. Elemen yang lebih besar seterusnya

Penerangan masalah

Penjelasan terperinci tentang idea

Untuk soalan ini, pilih yang lebih penyelesaian ganas.

Kami mula-mula memulakan tatasusunan res dengan panjang yang sama dengan nums untuk menyimpan hasil. [i]. Kami kemudiannya Melintasi dari j daripada nums2 untuk mencari tatasusunan yang lebih besar daripada nums[i] dan mengembalikannya Jika ia tidak menemuinya, kembalikan -1.

Kod dan hasil

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;
    }
}

2. Suhu harian

Penerangan tajuk

Penjelasan terperinci idea

Soalan ini juga menggunakan kaedah yang agak ganas. Sama seperti soalan sebelum ini.

Gelung berganda, jelas sekali kaedah ini mempunyai kerumitan masa yang lebih tinggi. Kaedah dengan kerumitan masa yang lebih rendah juga disediakan di sini.

Timbunan monoton

Apa yang kami kekalkan ialah tatasusunan jurang, iaitu tatasusunan hasil Mula-mula buat tindanan dan tentukan sama ada tindanan itu kosong, tolaknya terus ke dalam timbunan. Jika ia tidak kosong, bandingkannya Perbezaan antara elemen atas timbunan dan elemen semasa Jika elemen semasa lebih besar daripada elemen semasa, perbezaan itu dimasukkan ke dalam tatasusunan hasil yang sepadan dan elemen atas timbunan muncul dari timbunan Jika elemen semasa lebih kecil daripada tatasusunan hasil, ia ditolak ke timbunan.

Berikut ialah pautan ke animasi Adalah idea yang baik untuk mempelajari tindanan monotonik dalam animasi.

Kod dan hasil

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;
    }
}

3 Elemen seterusnya yang lebih besar II

Penerangan masalah

<.>Penjelasan terperinci idea

Idea soalan ini ialah timbunan monotonik Soalan 1 ialah penyelesaian kekerasan.

Prinsipnya sama seperti kaedah dalam soalan kedua, hanya perhatikan gelung. Pergi terus ke kod Jika anda tidak biasa dengannya, anda boleh menonton video soalan kedua dan kemudian lihat ini.

Kod dan hasil

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;
    }
}

Atas ialah kandungan terperinci Bagaimana untuk menggunakan timbunan monoton di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!