Untitled
unknown
java
23 days ago
3.2 kB
26
Indexable
Never
// leetcode 394 =================================================== class Solution { public String decodeString(String s) { Stack<Character> st = new Stack<>(); for(int i=0; i<s.length(); i++){ char ch = s.charAt(i); if(ch != ']'){ st.push(ch); } else { // retreive string after '[' StringBuilder sb = new StringBuilder(); while(st.size()>0 && st.peek()!='['){ sb.insert(0,st.pop()); } String toRepeat = sb.toString(); st.pop(); // removing '[' // retreive digits before '[' sb = new StringBuilder(); while(st.size()>0 && st.peek()>='0' && st.peek()<='9'){ sb.insert(0,st.pop()); } int count = Integer.parseInt(sb.toString()); // push string "repeating" times while(count > 0){ for(char c: toRepeat.toCharArray()){ st.push(c); } count--; } } } StringBuilder ans = new StringBuilder(); while(st.size()>0){ ans.append(st.pop()); } ans.reverse(); return ans.toString(); } } // next larger on left public static int[] nextLargerLeft(int[] arr){ int n = arr.length; int[] ans = new int[n]; Stack<Integer> st = new Stack<>(); st.push(-1); for(int i=0; i<arr.length; i++){ while(st.peek()!=-1 && arr[st.peek()] < arr[i]){ st.pop(); } int daysBefore = i - st.top(); ans[i] = daysBefore; st.push(i); } return ans; } // leetcode 901 ============================================== class StockSpanner { Stack<int[]> st = new Stack<>(); int currentDay = 0; public StockSpanner() { st.push(new int[]{-1,-1}); } public int next(int price) { while(st.peek()[0]!=-1 && st.peek()[1] <= price){ st.pop(); } int daysBefore = currentDay - st.peek()[0]; st.push(new int[]{currentDay,price}); currentDay++; return daysBefore; } } // leetcode 901 with class ========================================= class StockSpanner { class DayPrice { int currentDay; int currentPrice; public DayPrice(int currentDay, int currentPrice){ this.currentDay = currentDay; this.currentPrice = currentPrice; } } Stack<DayPrice> st = new Stack<>(); int currentDay = 0; public StockSpanner() { st.push(new DayPrice(-1,-1)); } public int next(int price) { while(st.peek().currentDay!=-1 && st.peek().currentPrice <= price){ st.pop(); } int daysBefore = currentDay - st.peek().currentDay; st.push(new DayPrice(currentDay, price)); currentDay++; return daysBefore; } }
Leave a Comment