Day7股票的最大利润+滑动窗口的最大值+把数字翻译成字符串

TODO:

1. 重做股票的最大利润
2. 把数字翻译成字符串，再好好理解下方法二的递归
3. 熟悉双端队列

一、剑指 Offer 63. 股票的最大利润(中等)

最开始想复杂了，理清楚思路就会简单许多。因为只交易一次，最大利润肯定是，每天的价值减去股票在这天以前的最小价值。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
       int n = prices.size();
       if( n == 0) return 0;
       int small = INT_MAX;
       int ans = 0;
       for(int i = 0; i < prices.size(); i++){
           if(prices[i] <small){small = prices[i];}
            ans = max(ans,prices[i]-small);
       }
       return ans;
    }
};

二、 剑指 Offer 59 - I. 滑动窗口的最大值(困难)

写了两个多小时的样子....貌似。从堆想到队列，再想到双端队列。
131205这个例子猜让我反应过来，但是用队列不能把比当前小的元素都出栈。
(官方题解的代码要清爽一些那就直接...）

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for (int i = 0; i < k; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
        }

        vector<int> ans = {nums[q.front()]};
        for (int i = k; i < n; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            while (q.front() <= i - k) {
                q.pop_front();
            }
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

三、剑指 Offer 46. 把数字翻译成字符串（中等）

😢没有想出来。
仔细想想找找转移方程应该是能够做出来的。
⭐注意：把整数转为字符串的技巧to_string
方法一：

class Solution {
public:
    int translateNum(int num) {
        if(num ==  0) return 1;
        string str = to_string(num);
        int a = 1, b =1,c;
        for(int i = 2; i <= str.size(); i++){
            auto pre = str.substr(i - 2, 2);//⭐
            if (pre <= "25" && pre >= "10") {
                c  = a+b;
            }
            a = b;
            b = c;
        }  
        return b;
    }
};

方法二：⭐
由于该方法的对称性也可以从后往前来看

class Solution {
public:
    int ans = 0;
    void bt(int num) {
        if(num == 0)    {
            ans += 1;
            return ;
        }
        bt(num / 10);
        if(num % 100 >= 10 && num % 100 < 26)
            bt(num / 100);

    }
    int translateNum(int num) {
        bt(num);
        return ans;
    }
};