---

1、買賣股票的最佳時機

121. 買賣股票的最佳時機

這里最容易想到的就是暴力枚舉，兩層for循環，i = 0， j = i + 1開始，但是這樣是O(n ^ 2)的時間復雜度，即使倒過來，選定一個值，找到這個值前面的一堆數字中的最小值，一減就能找到最大利潤，但是沒解決本質。不妨想一下，從第二個數開始往后走。每一次都找前面一堆數字的最小值，但后面要找的其實已經包含前面要找的了，也就是找第7個數字之前的最小值，一大部分已經在找第6個數字之前的最小值時找過了，只要把這個最小值和第6個數字一比較，誰小，誰就是找第7個數字之前的最小值，這樣，算法就是O(N)了。

    int maxProfit(vector<int>& prices) {int res = 0;for(int i = 0, prev = INT_MAX; i < prices.size(); ++i){res = max(res, prices[i] - prev);//先更新結果是因為如果先更新最小值，那么結果就沒法計算了prev = min(prev, prices[i]);}return res;}

2、買賣股票的最佳時機Ⅱ

122. 買賣股票的最佳時機 II

根據這個圖，可以畫一個折線圖，每天的價格就是一個點，連接起來所有點。思路就是每次選一個點，都找到從這個點開始持續遞增后的點，如果價格出現減少或不變，那就停止，這樣每個增長趨勢內可得到的最大利潤都被算進來了，就能得到最大利潤。

為了找到嚴格遞增過程中最大的點，可以用雙指針來控制。另一個方法是把每段交易變成一天一天，這個思路是只要第二天的數字比第一天大，那就加上第二天的數字。

        //雙指針int ret = 0, n = prices.size();for(int i = 0; i < n; ++i){int j = i;while(j + 1 < n && prices[j + 1] > prices[j]) ++j;ret += prices[j] - prices[i];i = j;}return ret;//拆分int ret = 0;for(int i = 1; i < prices.size(); ++i){if(prices[i] > prices[i - 1])ret += prices[i] - prices[i - 1];}return ret;

3、K次取反后最大化的數組和

1005. K 次取反后最大化的數組和

理解這道題后會發現，應當先對最小的負數取反，才能得到最大和。從負數開始，從小到大，一個個取反。假設m是負數個數，m > k，那就把前k小的負數轉化成正數；m == k，把所有負數全部轉化為正數；m < k，先把所有負數都取反，剩余的次數k - m，如果它是偶數，那么就無影響，可以只對一個數字取反偶次數，那么這個數不變，如果是k - m是奇數，那就得把現有正數（因為已經取反了所有負數）中最小的那個數取反奇次數，就可以拿到最大數組和了。

    int largestSumAfterKNegations(vector<int>& nums, int k) {int m = 0, minElem = INT_MAX, n = nums.size();for(auto x : nums){if(x < 0) m++;minElem = min(minElem, abs(x));}int ret = 0;if(m > k){sort(nums.begin(), nums.end());for(int i = 0; i < k; ++i){ret += -nums[i];}for(int i = k; i < n; ++i){ret += nums[i];}}else{for(auto x: nums) ret += abs(x);if((k - m) % 2){ret -= minElem * 2;}}return ret;}

4、按身高排序

2418. 按身高排序

我們可以創建一個新數組pair<int, string>這樣名字和數字都在一起，對這個數組排序就行。

解法二是利用哈希表存映射關系。對身高數組排序，根據結果在哈希表里找名字即可。

以上兩種思路類似，這里走一個不同的思路，雖然要排序，但不是真正的排序，對其中的元素不做手腳，但要能按照給出最終的順序對應的元素。這里創建一個下標數組，只對下標數組排序，根據下標數組排序后的結果，找到原數組的信息。

    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {int n = names.size();vector<int> index(n);for(int i = 0; i < n; ++i){index[i] = i;}sort(index.begin(), index.end(), [&](int i, int j){return heights[i] > heights[j];});vector<string> ret;for(auto i : index){ret.push_back(names[i]);}return ret;}

5、優勢洗牌

870. 優勢洗牌

這道題的意思是給了兩個數組，返回一個最終的數組，比如例1，
2 7 11 15
1 10 4 11
第一個位置可以放2，比1，第二個位置可以放11，比10大，第三個可以放15，比4大，但這樣第四個位置就放不了，所以這樣優勢不是最大化，第三個位置放7，第四個位置可以放15，這樣優勢就最大化了。

這道題可以用田忌賽馬的思路，即，如果比不過，就放到另一個數組最大的那個對應的位置，如果能比過，那就直接比。在這之前，先排序一遍。

按照這個思路，看例2，我們會得到[12, 24, 32, 8]這個答案，和示例不一樣，這是因為，我們是按照排序后的數組去做的結果，這個結果還需要對應上原先數組，所以還得改一下順序，才是最終結果。

為此，要和上一個題一樣，用下標數組來做。

    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();//排序sort(nums1.begin(), nums1.end());vector<int> index2(n);for(int i = 0; i < n; ++i) index2[i] = i;sort(index2.begin(), index2.end(), [&](int i, int j){return nums2[i] < nums2[j];});//田忌賽馬vector<int> ret(n);int left = 0, right = n - 1;for(auto x : nums1){if(x > nums2[index2[left]]) ret[index2[left++]] = x;else ret[index2[right--]] = x;}return ret;}

6、最長回文串

409. 最長回文串

按照題目，回文串的長度是偶數或者奇數，從中間切一刀，兩邊都一樣，中間切開的那個位置沒有元素或者只有一個元素。所以我們可以這樣想，一個字符串中可能出現的所有字符，記錄下每個字符出現的次數，如果次數為偶數，就可以兩邊都放，那就是直接加上這個數字；如果是奇數，就-1，然后兩邊都放。所有次數可能不止有一個奇數，但奇數的個數不用擔心，按照上面的做法，偶數就直接加，奇數就-1加上，算出來的長度如果等于原字符串長度，說明都是偶數，那就不用繼續處理，直接返回；如果小于原字符串，說明出現了奇數，那么就+1，再返回。

    int longestPalindrome(string s) {int hash[127] = {0};for(char ch : s) hash[ch]++;int ret = 0;for(int x : hash){ret += x / 2 * 2;//這樣奇數偶數都能計算}return ret < s.size() ? ret + 1 : ret;}

7、增減字符串匹配

942. 增減字符串匹配

題目的意思就是給定一個字符串，比如IDI，那就增減增，從0123四個數字中選擇來組成數組。

這道題體現的貪心是，為了符合字符串展現的規則，遇到I時，應當選擇當前最小的那個數，遇到D時，選擇當前最大的那個數。

    vector<int> diStringMatch(string s) {int left = 0, right = s.size();vector<int> res;for(auto ch : s){if(ch == 'I') res.push_back(left++);else res.push_back(right--);}res.push_back(left);return res;}

結束。