国庆放假回家不小心少写了一天。

力扣

这周做了很多贪心相关的题目，写不太明白，找不到套路，感觉每道题思路都不太一样。

11. Container With Most Water

写过不少双指针题目了，但第一次写头尾双指针的，头回见确实想不到。具体贪心不会证，大致就是容量与较小边强相关，所以试图移动较小边指针以寻找更大较小边。

class Solution {
public:
    int maxArea(vector<int>& height) {
        auto i = 0;
        auto j = height.size() - 1;
        int maxa = 0;
        while (i < j ) {
            int area = (j - i) * min(height[i], height[j]);
            maxa = max(maxa, area);
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return maxa;
    }
};

$O(n)$时间复杂度，十分优美。

739. Daily Temperatures

单调栈的简单应用但又不完全是套模板，更像是一个要自己实现“cmp函数”的单调栈。

单调栈（Monotonic Stack ）就是一个保证单调性的栈，本身概念以及实现及其简单，甚至不屑于封装，每次插入时把不满足单调性的元素直接弹出即可。

这题我们的单调栈不存数组元素而是存下标，这样我们才得以计算下标间的差值。从左到右遍历，每个元素都插入单调栈。当遇到要弹出的情况则刚好是找到目标下标的情况，此时将下标插入答案数组即可。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size());
        stack<int> maxT;
        for (int i = 0; i < temperatures.size(); i++) {
            while (!maxT.empty() && temperatures[i] > temperatures[maxT.top()]) {
                ans[maxT.top()] = i - maxT.top();
                maxT.pop();
            }
            maxT.push(i);
        }
        return ans;
    }
};

时间复杂度$O(n)$，挺好。

215. Kth Largest Element in an Array

堆

这题用priority_queue太简单，主要谈谈如何用数组实现堆。我们选用cpp的vector，实现一个最大堆。

存储堆只需要一个数组即可，std::vector<int> heap

堆的每个节点都有两个子节点，根据int类型数字的除法性质观察可得：数组元素下标除以2对应的元素即为父节点。为了利用这个性质，我们的heap要有一个哨兵位，即首位下标为0的位置。所以，我们的根节点即堆顶，就是heap[1]。

我们先实现获取堆顶的方法。

int heapTop(std::vector<int> &heap) {
    if (heap.size() > 1) return heap[1];
    else return 0;
}

然后是插入元素的方法。我们将元素插入到堆底，然后再进行维护。这样我们就只需要移动数组的一部分，保证了时间复杂度是$O(\log n)$

void insert(std::vector<int> &heap, int value) {
    // 初始化堆要插入哨兵元素。
    if (heap.empty()) heap.push_back(0);
    heap.push_back(value);
    // 插入后开始维护堆
    // 由于插入在堆底，所以我们要swim这个元素浮到对的地方
    int index = heap.size() - 1;

    while (index >= 1 && heap[index / 2] < heap[index]) {
        swap(heap[index], heap[idnex / 2]);
        index /= 2;
    }
}

插入我们swim了，删除元素我们则要sink。什么意思呢？我们删除堆顶元素首先要将其与堆底元素交换，再弹出堆底元素，然后从堆顶开始sink这个元素到合适位置。

void delete(std::vector<int> heap) {
    if (heap.size() <= 1) return; // 只有哨兵位，堆不完整视为空堆。
    swap(heap[1], heap.back());
    heap.pop_back();

    // 开始维护堆，sink
    int size = heap.size() - 1;
    int k = 1;
    while (2 * k <= size) {
        int j = 2 * k;
        if (j + 1 <= size && heap[j] < heap[j + 1]) j++; // 保证不越界的情况下访问更大的子节点，这样堆中最大节点才能到达堆顶。
        if (heap[j] < heap[k]) break; // 找到位置了
        swap(heap[j], heap[k]);
        k = j;
    }
}

快排选择

这题也是经典的快排选择题。由于快速排序递归分治的性质，我们可以每次只对需要的那个子数组递归，以找到第k个，这样保证了时间复杂度是$O(n)$。

我们这里为方便，假定找到数组正序第k个元素。

int quickSelect(std::vector<int> &nums, int lo, int hi, int k) {
    if (lo >= hi) return nums[k];
    int pivot = nums[lo];
    int left = lo, right = hi;
    while (left <= right) {
        while (nums[left] < pivot) left++;
        while (nums[right] > pivot) right--;
        if (left <= right) swap(nums[left], nums[right]);
    }
    // 选择性递归，right为分界点。
    if (k <= right) return quickSelect(nums, lo, right, k);
    else return quickSelect(nums, right + 1, hi, k);
}

146. LRU Cache

纯粹的基本功题目。实现一个LRU Cache。用unordered_map和list实现。