LeetCode 75
Online Stock Span
- Problem
- LC 901
- Topic
- Monotonic Stack
- File
- official75_LC901OnlineStockSpan.java
- Path
- pkg5leetcode/official75/official75_LC901OnlineStockSpan.java
- Package
- pkg5leetcode.official75
- Command
- java pkg5leetcode/official75/official75_LC901OnlineStockSpan.java
- Approach
- Monotonic stack of price/index pairs.
- Complexity
- Time O(1) amortized, Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.official75;2 3/*4 * Online Stock Span | LC 9015 * APPROACH: Monotonic stack of price/index pairs.6 * COMPLEXITY: Time O(1) amortized, Space O(n)7 */8import java.util.*;9 10public class official75_LC901OnlineStockSpan {11 static class StockSpanner {12 Deque<int[]> st = new ArrayDeque<>();13 14 int next(int price) {15 int span = 1;16 while (!st.isEmpty() && st.peekLast()[0] <= price) span += st.pollLast()[1];17 st.addLast(new int[]{price, span});18 return span;19 }20 }21 22 public static void main(String[] args) {23 StockSpanner sp = new StockSpanner();24 check(sp.next(100) == 1, "case1");25 check(sp.next(80) == 1, "case2");26 check(sp.next(60) == 1, "case3");27 check(sp.next(70) == 2, "case4");28 check(sp.next(60) == 1, "case5");29 check(sp.next(75) == 4, "case6");30 check(sp.next(85) == 6, "case7");31 System.out.println("all tests passed");32 }33 34 static void check(boolean cond, String name) {35 if (!cond) throw new AssertionError("FAILED: " + name);36 System.out.println(" PASS " + name);37 }38}