Stack

Key points

• ArrayDeque Front(First) [6, 5, 4, 1, 2, 3] Rear(Last)

• Stack push to Front and pop from Front

• Queue offer to Rear and poll from Front

  • Queue offerFirst to Front, pollLast from Rear

Example:

Deque<Integer> q = new ArrayDeque<>();
q.offer(1);
q.offer(2);
q.offer(3);
q.offerFirst(4);
q.offerFirst(5);
q.pollLast();
q.push(7);
q.push(8);
q.push(9);
q.pop();
q.toString(); // [8, 7, 5, 4, 1, 2]

Calculator / evaluate expression

Track at least 3 variables: num1, op1, currNum, {currOp}, {num3} ...

1. currOp is +/-, or op1 && currOp both are * or /: currNum = eval(num1, op1, currNum)

2. other cases: currNum = eval(currNum, currOp, num3). Because we don't know whether it is left parenthesis or num3 after currOp, let's push currNum, currOp to stack and do calculation later.

• 0150. Evaluate Reverse Polish Notation
• 0282. Expression Add Operators
• 0224. Basic Calculator
• 0227. Basic Calculator II
• 0770. Basic Calculator IV
• 0772. Basic Calculator III
• 0736. Parse Lisp Expression
• 0439. Ternary Expression Parser

Monotonic Queue problem

Maintain increasing or decreasing sequence.

https://1e9.medium.com/monotonic-queue-notes-980a019d5793

• 0084. Largest Rectangle in Histogram

  • 0085. Maximal Rectangle
• 0239. Sliding Window Maximum
• 0739. Daily Temperatures
• 0862. Shortest Subarray with Sum at Least K
• 0907. Sum of Subarray Minimums: This is new
• 0581. Shortest Unsorted Continuous Subarray

Lexicographical order

Find a way to fast forward:

• 0060. Permutation Sequence
• 0440. K-th Smallest in Lexicographical Order
• 0179. Largest Number: Not lexico order, the customized comparator is key.
• 0321. Create Maximum Number
• 0031. Next Permutation
• 0670. Maximum Swap
• 0681. Next Closest Time
• 0564. Find the Closest Palindrome
• 0738. Monotone Increasing Digits

Select largest/smallest k number from array

• 0321. Create Maximum Number
• 0402. Remove K Digits