LeetCode 280 Wiggle Sort
链接：https://leetcode.com/problems/wiggle-sort/
方法：贪心、找规律
时间复杂度：O(n)
想法：经典题之一，我记得在我连LeetCode easy都做不出来的岁月里就遇到过这个题并看过题解了，所以假设说问我这道题是怎么想到的，我也说不出来。反正题目要求是nums[0] <= nums[1] >= nums[2] <= nums[3]...，那比方说我们从index 1开始遍历，然后下标是奇数的相对来说在最后应该放一些比较大的元素，下标是偶数的会放一些比较小的元素。假如下标是奇数，但它比它前一个元素小，那我们就把这俩元素换过来，为什么这样呢？因为换过来的话，它俩相对的大小关系就合法了，然后换过去之后，因为偶数下标原本就应该放一些比较小的元素，原本我们在没遍历这个值之前，i-1处的值已经合法了，然后现在换过来一个比原来更小的值，那当然可以维持前面那个不等式。同理如果下标是偶数，但比前一个元素大，那也换走拉倒。如果前一个元素和这个元素值一样，换与不换没有区别。综上，一套贪心换到最后就完了。
代码：
class Solution {
public void wiggleSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
if ((i % 2 != 0) == (nums[i] < nums[i - 1])) {
int tmp = nums[i - 1];
nums[i - 1] = nums[i];
nums[i] = tmp;
}
}
}
}
LeetCode 316 Remove Duplicate Letters
链接：https://leetcode.com/problems/remove-duplicate-letters/
方法：单调栈
时间复杂度：O(n)
想法：和1081题一模一样。这个题在我做了好几遍、复习了好几遍的时候，我每次回来做还是做不对。主要是能想到要用单调栈，但没想到单调栈往外弹的策略是什么。总之解释一下这道题的做法。首先题目让我们删掉所有重复的字母，并且使最后得到的字符串字典序最小。因为一个字符串里哪些字符会重复出现是一个确定的东西，然后在这些可能的字符串里面找字典序最小，仔细想想会发现，假如说xyzciac，前面有个c，后面有个c，两个中间有一个a，那么既然中间出现了a，就应该留后面那个c。如果两个重复的字符之间，没有比它小的字符，那就留前面那个，否则就留后面那个。那么怎么去实现上面用文字说的策略呢？
首先用一个哈希表（数组）cnt，扫一遍字符串，记录每个字母出现的次数。然后重扫一遍字符串，每次扫到一个字符，把cnt对应的值减一，那么cnt所代表的就是在此之后，相同的字母还会出现多少次。开一个数组visited，代表每个元素是不是已经在之前被放好了。在字符串第二次遍历的时候，如果visited对应的是true，就说明之前这个字母已经放完了，那就continue。否则的话，就是针对栈的操作，while栈顶大于当前字符，并且栈顶在后面还会出现，那说明我们要留后面那个，所以栈顶元素就会被标记为visited=false，然后从栈里弹出来。栈操作结束，当前字符入栈，并标记为visited。这么做为什么是对的？某一字母的在visited中被标记为true的时候，一定发生在入栈，入栈一定发生在一系列弹栈操作结束，那你后面访问的时候，如果字母对应的visited是true，说明从这个字母被放进来，一直到你当前遍历到的这里，他都没被弹出去，因为在这之前它后面肯定至少还有一次出现（当前这个下标），因此说明这一段当中没有比它还小的字符把它踢出去，所以当前这个地方直接continue。最后栈里剩的就是结果字符串需要的。
两个小技巧：1. 使用ArrayList而不是Stack，因为Stack继承自Vector，Vector是线程安全的，相对来说比较慢，如果对此不熟的话去被JCF。并且，在最后产生结果时，我们生成的字符串是正着从栈里面拿元素，真用Stack的话弹出来是反的，还得再reverse一次，没必要。2. List里面预先放一个元素叫'0'，因为这题说了字符串里只有小写英文字母，在做栈的操作时，如果不做这一步，我们将不可避免地每次需要判定栈是不是为空。为了避免这一点，我们放入'0'，'0'的ASCII比所有小写字母全小，所以原字符串中没有任何字符能把它踢出来，所以栈永远不为空，于是就避免了判定栈为空的麻烦。
代码：
class Solution {
public String removeDuplicateLetters(String s) {
int[] cnt = new int[26];
boolean[] visited = new boolean[26];
List<Character> cur = new ArrayList<>();
cur.add('0');
int n = s.length();
for (int i = 0; i < n; i++) {
cnt[s.charAt(i) - 'a']++;
}
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
cnt[c - 'a']--;
if (visited[c - 'a']) {
continue;
}
while (cur.get(cur.size() - 1) > c && cnt[cur.get(cur.size() - 1) - 'a'] > 0) {
visited[cur.get(cur.size() - 1) - 'a'] = false;
cur.remove(cur.size() - 1);
}
visited[c - 'a'] = true;
cur.add(c);
}
StringBuilder sb = new StringBuilder();
for (int i = 1; i < cur.size(); i++) {
sb.append(cur.get(i));
}
return sb.toString();
}
}
