理论

常见应用

• 1. 找到最小次数完成某事
• 2. 找到最大次数满足某条件

Problems

1. 找到最小次数完成某事

452. Minimum Number of Arrows to Burst Balloons区间题，总是选择较早结束的区间
621. Task Scheduler至少为众数出现的次数 - 1）* (n+1)+最后一行（最后行为不同众数的个数）；若比这个众数有更多非众数，则不受间隔限制
2268. Minimum Number of Keypresses将字母出现的次数逆序排序，遍历， 每9个字母，click += 1
3326. Minimum Division Operations to Make Array Non Decreasing从右到左遍历，每次比右边数字大，则除以properDivisor
1058. Minimize Rounding Error to Meet Target理论上需要离ceil最近的前n1个，离floor最近的n2个。但是如何确定n1, n2呢？先全部按照floor计算得到floorSum，同时将distanceToCeil-distanceToFloor放入heap中，floorSum和target的距离k即为需要添加ceil的个数，heapq中pop出前k个加入res，即可
2366. Minimum Replacements to Sort the Array逆序遍历，使得元素尽可能的大，对于nums[i] > nums[i+1], 为了使得最前个元素经可能的大，可以将nums[i]以ceil(nums[i]/nums[i+1])个格子均匀分布。
1526. Minimum Number of Increments on Subarrays to Form a Target Array只考虑相邻两个的增值
1007. Minimum Domino Rotations For Equal Row只有top[0]或bottom[0]可能成为最终value， 分别判断让其成为最终值，需要几次flip
818. Race Carbfs， 仅当(pos + speed < target & speed < 0)或(pos + speed > target & speed > 0)时调转方向\

2. 找到最大次数满足某条件

948. Bag of Tokens1）若要加score， 使用min power 2)若要加power， 增加max power => 排序+双指针+greedy
1405. Longest Happy String可有maxheap做，但greedy可以直接有三个变量记录得\

3. 根据两者关系排序，得到前k个

1029. Two City Schedulingcost[i][0] - cost[i][1]为将第i个人送到A而不是B所导致的额外cost, 选择额外cost最小的n个人送至A,剩下的人送至B
2611. Mice and Cheese类似1029\

4. 不断拓宽边界

55. Jump Game不断更新可以达到最远距离
769. Max Chunks To Make Sorted遍历，更新最大num， 若Maxnum == i, 则代表之前出现的所有数都可以在<=i的位置, res += 1\

Jump Game Addition to keeping the max frontier, also keep track of the level. At every level, propagate the next frontier element between last visited and current frontier, level++. Surprised to see it is labelled as hard.

Remove Duplicate Letters Solution #1: solved by greedy algo + recursion. The idea is everytime, find the right most smallest letter within the range. if some letter no longer again appear, then it is considered out of the range. Solution #2: solved by stack by making sure the stack always have the smallest lexicographical order; We walk through the array, if encounter future word which has is not in the current stack(this is done by use a separated visited array), then we add it to the current stack. To do so, if it has smaller lexicographical order than the top of the stack, and the stack top has future occurrences, then pop it out until either of the two conditions is not met. push in the element.

non-overlapping-intervals

sort the interval, only include the interval ends earlier.

can-place-flowers

minimum-domino-rotations-for-equal-row

多种方法，其中一种可以是two pass,分别判断翻到a[0], 或是b[0]的次数，取其较小者。