首頁 > Java > java教程 > Java怎麼運用單調棧

Java怎麼運用單調棧

WBOY
發布: 2023-05-17 10:07:05
轉載
1142 人瀏覽過

1.下一個更大元素

題目描述

Java怎麼運用單調棧

#思路詳解

這一題就選取比較暴力的解法了。

我們先初始化一個與nums等長度的res數組用來儲存結果,我們遍歷取出nums中的值,到nums2中尋找,直到找到nums2[j] == nums[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;
    }
}
登入後複製

Java怎麼運用單調棧

2.每日溫度

題目描述

Java怎麼運用單調棧

想法詳解

這一題也是使用比較暴力的方法。同上一題一樣。

兩重循環,顯然這種方法時間複雜度較高。這裡也提供一種時間複雜度較低的方法。

單調棧

我們維護的是一個差距數組也就是結果數組,首先創建一個棧,判斷棧是否為空,若為空直接入棧,若不為空則比較棧頂元素與目前元素,若目前元素大於目前元素就把差值放入對應結果陣列同時棧頂元素出棧,若目前元素小於結果陣列則入棧。

這裡給一個動畫連結很好董,動畫學單調堆疊。

程式碼與結果

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;
    }
}
登入後複製

Java怎麼運用單調棧

3.下一個更大元素II

題目描述

Java怎麼運用單調棧

思路詳解

本題的思路呢單調棧,問題一暴力破解,這個題要使用單調棧了。

原理同第二題的方法一樣,就在循環上註意一下就可以了。直接上程式碼,不董的可以看第二題的影片再來看這個喔。

程式碼與結果

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怎麼運用單調棧

#

以上是Java怎麼運用單調棧的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:yisu.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板