Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間3年前 (2022/11/09 10:55)推噓3(3推 0噓 5→)

留言8則, 3人參與討論串93/719 (看更多)

901. Online Stock Span 其實我看不太懂題目在工殺小(也不想知道)，總之我們要設計一個類別，每次可以對該類別offer一個整數，你要返回該整數插入位置往前算共有幾個小於等於他的連續數字( 包括他自己)。 Example： Input ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"] [[], [100], [80], [60], [70], [60], [75], [85]] Output [null, 1, 1, 1, 2, 1, 4, 6] Explanation StockSpanner stockSpanner = new StockSpanner(); stockSpanner.next(100); // return 1 stockSpanner.next(80); // return 1 stockSpanner.next(60); // return 1 stockSpanner.next(70); // return 2 [100 80 60 70] stockSpanner.next(60); // return 1 stockSpanner.next(75); // return 4 [100 80 60 70 60 75] stockSpanner.next(85); // return 6 思路： 1.因為要從當前位置往前檢查，要記錄之前的結果，所以直覺的想到用 stack 做。 2.總之就把當前的數字與頂端比較，如果小於頂端就返回1，否則不斷的從頂端取出元素直到不能再取，過程不斷的+1 Java Code： -------------------------------------------- class StockSpanner { private Stack<Integer> stack; private Stack<Integer> tmp; public StockSpanner() { stack = new Stack<>(); tmp = new Stack<>(); } public int next(int price) { int count = 1; while (!stack.isEmpty() && stack.peek() <= price) { tmp.push(stack.pop()); count++; } while (!tmp.isEmpty()) { stack.push(tmp.pop()); } stack.push(price); return count; } } --------------------------------------------- 3.好喔但是直接做的結果吃了TLE 那就只能想辦法改良了 4.其實取出來的元素沒必要塞回去，我們改用一個pair來儲存上次這個點往前查找的結果，陣列[0]表示價錢[1]表示有幾個，這樣每次查詢查出來的都是一個區間了 Java Code： --------------------------------------------- class StockSpanner { private Stack<int[]> stack; public StockSpanner() { stack = new Stack<>(); } public int next(int price) { int count = 1; while (!stack.isEmpty() && stack.peek()[0] <= price) { count += stack.peek()[1]; stack.pop(); } stack.push(new int[] {price, count}); return count; } } --------------------------------------------- 大guy是這樣 -- https://i.imgur.com/fHpKflu.jpg