liyunrui

class MaxStack:
    """   
    push 1, 5
    tmp_stack = []
    stack = [5,1]
    max_stack = [5,5]
    
    這題多了一個pop max 是最難的地方
    tmp = stakc.pop() # 1
    tmp_max = max_stack.pop() # 5

liyunrui

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    """
    root->left->right(pre-order)
    left->right->root(post-order)

liyunrui

class Solution:
    """
    1.有加號, 減號, 乘號, 除號!沒有括號
    2.All the integers in the expression are non-negative integers, which means there's no leading negative sign and no 3*-5
    10+3-2
          i
        
    3+5
     i
    1.遇到+/-號, 我們就可以parse下一個num, 然後根據sign把num放進stack

liyunrui

class Solution:
    """
    What's disibution of input string s?
    沒有乘號, 只有加號和減號!
    
    當只有加號和減號,沒有括號和乘號!
    1-1
      i
      num=1
      sign=-1

liyunrui

class Solution:
    """
    "2*(5+5*2)/3+(6/2+8)"
               i
    """
    def calculate(self, s: str) -> int:
        def cal_update(op, num, stack):
            if op == "+":
                stack.append(num)
            elif op == "-":

liyunrui

class Solution:
    """
    Brute Force: 已當前高度為邊界,去找出所有可能的rectangle
        we traverse the array.
        For each cur_h, we enumerate all valid rectangle and calculater area
        by w * min_h in the subarray.
        T:O(n^2)
        S:O(1)
    
    Can we optimise?

liyunrui

class MedianFinder:
    """
    Binary Search + Insert
    T: O(logn) +O(n) = O(n) for add function O(1) for findMedian.
    S: O(n)
    我們用一個array不斷存放新進來的data, as time goes, it's become inefficient in terms of space(not scalable)
    
    Two heaps: max heap+min_heap+balance
    T: 3*O(logn) for add function O(1) for findMedian.
    S: O(n)

liyunrui

class KthLargest:
    """
    Binary Search+ Insert
    [2,4,5,8]
    k=3
    add 3 -> [2,3,4,5,8]-->return 4
                  -
    add 4 -> [2,3,4,5,5,8]-->return 5
                    -
    [2,3,4,5,5,8,10]

liyunrui

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        balance = 0
        n = len(s)
        ans = 0
        for i in range(n):
            if s[i] == "R":
                balance+=1
            else:
                balance-=1

liyunrui

class Solution:
    """
    what's distribution of input string s:
        ---> s consists of English letters and digits. At most, 26+10 numbers
        
    Heap solution and Sorting takes O(nlogn)
    
    Bucket sort 
    
    freq array=[0,1,2,3,..,max_freq]