2020-02-05 刷题2（数组）

189 旋转数组

数组整体移位的题目。
最简单的就是，用另一个数组来暂时存放，时间复杂度O(n), 空间复杂度O(n).
之前离散数学里，学过一种原地操作的解法，比如：
[1, 2, 3, 4, 5, 6], k=2
则可以构成两个环，分别为：[1,3, 5], [2,4,5];
在每个环内，设置一个变量cur_start来记录环起点，每次将环中前一个元素复制到后一个元素中，如果后一个元素的下标等于环起点，则这个环全部移位完成；将cur_start加1来操作下一个环。设置一个变量c来记录完成移位的元素个数。
时间复杂度：O(n)
空间复杂度：O(1)
代码：

时间：98.03%， 空间：5.04%
class Solution {
public:
void rotate(vector<int>& nums, int k) {
    int a_len = nums.size();
    k = k % a_len;
    if (k == 0)
        return;
    int c = 0;
    int cur_start = 0;
    int s = 0, t;   // start_pos, end_pos
    int last = nums[0], tmp;   // tmp var to store end_pos element
    while(c < a_len){
        t = (s + k) % a_len;
        
        // use last element to fill in current position
        tmp = nums[t];
        nums[t] = last;
        last = tmp;
        
        if(t == cur_start){
            cur_start++;
            s = cur_start;
            last = nums[s];
        }
        
        else s = t;
        c++;
    }
}
};

还有另一种解法也很巧妙，经过步长为k的移位后，后面k个元素被反转到了前面，剩下的前面的元素留在了后面。

官方题解

经过三次翻转，也可以使得各个元素归位。

---

122 买卖股票的最佳时机II

一定要注意边界条件，不控制边界条件可能会runtime error的

一开始想了一种动态规划的解法，将i买入，j卖出的最大利润记做P(i,j)，然后写出递推公式。但是这种做法的时间复杂度是O(n^3)，运行到最后一个测试样例就超时了。

后来分析问题发现，对于a1, a2, a3, a4这样的序列，如果a1<a2, a1<a4, a3<a4, a3<a2,也就是这四个数第二和第三个是局部最大值和局部最小值，则a1买入，a4卖出的利润一定小于a1买入a2卖出a3买入a4再卖出。也就是说，对于一个序列，局部最小值一定是可以买入的，局部最大值一定是可以卖出的，这样至少不会使得最终的总利润变低。

因此，最后的解法是，在数组最左侧和最右侧分别设置一个最大值和最小值作为哨兵，从左到右遍历数组，找到局部最小值就买入，找到局部最大值就卖出。

即使这样，还有一个问题，如果连续几天的股票价格都一样，就很难定义局部最值了。因此，首先遍历一遍数组，将连续的重复值去掉，然后再开始股票买卖。这里，去重用的是双指针，也是一个非常巧妙的做法，可以参考26. 删除排序数组中的重复项。
时间复杂度：O(n)
空间复杂度: O(1)
代码：

时间：70.09%， 内存：5%
class Solution {
public:
int maxProfit(vector<int>& prices) {
    int vec_len = prices.size();
    // remove continuous repeated element
    int p = 0, q = 1;
    for(;q < vec_len; q++){
        if (prices[q] != prices[p]){
            p++;
            prices[p] = prices[q];
        }
    }
    vec_len = p + 1;
    if (vec_len <= 1)
        return 0;
    
    // set guardance
    if (vec_len == prices.size())
        prices.push_back(0);
    else prices[vec_len] = 0;
    prices.insert(prices.begin(), 2147483647);
    
    int profit = 0;
    int in, out;
    bool is_out = false;
    for(int i = 1; i <= vec_len; i++){
        if (!is_out){
            // find local min
            if (prices[i] < prices[i-1] && prices[i] < prices[i+1]){
                in = prices[i];
                is_out = true;
            }
        }
        else{
            // find local max
            if (prices[i] > prices[i-1] && prices[i] > prices[i+1]) {
                out = prices[i];
                profit += (out - in);
                is_out = false;
            }
        }
    }
    return profit;
}
};

另一种解法，是不需要提前去掉连续重复的元素，只要通过while循环，来找到峰值和谷值，只要将while循环中第二个判断条件设为小于等于（或大于等于），就可以达到排除相等元素的作用。

time: 97.64%, memory: 42.59%
class Solution {
public:
int maxProfit(vector<int>& prices) {
    int vec_len = prices.size();
    if (vec_len <= 1)
        return 0;

    int profit = 0;
    int valley = prices[0], peak = prices[0];
    int idx = 0;
    while(idx < vec_len){
        // find valley
        while(idx < vec_len - 1 && prices[idx + 1] <= prices[idx]){
            idx++;
        }
        valley = prices[idx];
        idx++;
        if (idx >= vec_len)  // 不加入这一判断会溢出
            break;
        // find peak
        while(idx < vec_len - 1 && prices[idx + 1] >= prices[idx]){
            idx++;
        }
        peak = prices[idx];
        idx++;
        if (peak > valley)
            profit += (peak - valley);
    }
    return profit;
}
};

---