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