贪心算法

11. 盛最多水的容器

思路：双指针从外向内移动，每次移动指针中指向较小值的那一侧。因为容量受Math.min(a[i], a[j])*(j-i)决定，移动指针一定会减小宽度 j-i ，只有提升高度才可能找到更大的容量，因此只有移动较小侧的指针才有可能提升高度。

134. 加油站

环形的路和加油站，问从哪里可以环绕一圈。
思路：如果x到不了y+1（但能到y），那么从x到y的任一点出发都不可能到达y+1。因为从其中任一点出发的话，相当于从0开始加油，而如果从x出发到该点则不一定是从0开始加油，可能还有剩余的油。既然不从0开始都到不了y+1，那么从0开始就更不可能到达y+1了

316. 去除重复字母

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）
思路：先想一个简单的问题，如何在一个字符串中去除一个字符使得字典序最小？由于字符串中越靠前的字符对字典序影响越大，因此，找出满足s[i]>s[i+1]的最小的i，就是应该去除的字符【关键字符】。而对于题目，直观的做法是对每个重复的字符，循环重复次数-1，去除每次的关键字符。然而这种做法会保留大量的中间字符串。
可以通过单调栈简化：从前往后遍历，每遍历一位时，就处理目前已经扫描过的位置的关键字符，则在遍历第 i 位时，关键字符只可能出现在第 i 位以后。通过单调栈维护去除了关键字符后的字符串，为了实现最小字典序，单调栈以从底到顶字符递增的方式记录前 i-1 个字符中保留的字符。如果当前字符 s[i] 已经存在于栈中，说明当前栈维护的字符串的字典序已经优于将s[i]这种字母排在目前栈顶后面的位置的字典序，因此可以直接丢弃当前字符；如果当前字符 s[i] 小于栈顶，且栈顶元素所剩总数仍然大于1，说明栈顶字符是可以舍弃的关键字符，应该去除，一直去除到栈空或者当前字符>=栈顶字符。去除完成后，将当前字符加入栈顶。过程中，需要用Map维护各个字符的所剩总数。

767. 重构字符串

给定一个字符串，重构使得新字符串相同元素不相邻。
思路：先通过个数最多的字符 的个数是否大于(n+1)/2+1，判断是否有重构的可能。如果有，则优先安排出现次数多的字符。通过大顶堆维护字符串中所有种类的字符，从底到顶出现次数递增。每次抽取顶上两种字符各一个，拼在新字符串的后面，然后更新大顶堆，直到大顶堆为空或者只剩一个元素，只剩一个元素时直接将元素拼接在新字符串后面。