Greedy

super washing machine

假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。

贪心魔法。

class Solution {
public:
    int findMinMoves(vector<int> &machines) {
        int tot = accumulate(machines.begin(), machines.end(), 0);
        int n = machines.size();
        if (tot % n) {
            return -1;
        }
        int avg = tot / n;
        int ans = 0, sum = 0;
        for (int num: machines) {
            num -= avg;
            sum += num;
            ans = max(ans, max(abs(sum), num));
        }
        return ans;
    }
};

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

三遍循环的优雅贪心：

class Solution {
public:
    int trap(vector<int>& height) {
        int size = height.size();
        vector<int> left_max(size), right_max(size);
        left_max[0] = 0;
        right_max[size - 1] = 0;
        int max = height[0];
        for (int i = 1; i < size; ++i){
            left_max[i] = max;
            max = std::max(max, height[i]);
        }
        max = height[size - 1];
        for (int i = size - 2; i >= 0; --i){
            right_max[i] = max;
            max = std::max(max, height[i]);
        }
        int res = 0, con;
        // final loop
        for (int i = 0; i < size; ++i){
            con = std::min(left_max[i], right_max[i]);
            res += (con - height[i] < 0) ? 0 : con - height[i];
        }
        return res;
    }
};

用栈发现不得不动态离散化的丑陋贪心：

class Solution {
public:
    int trap(vector<int>& height) {
        stack<pair<int, int>> s; // id, height
        map<int, int> d;
        int ans = 0;
        for (int i = 0; i < height.size(); i++) {
            int H = height[i];
            d[H]++;
            if (!s.empty()) {
                int last = 0;
                for (auto it = d.begin(); it != d.end(); it++) {
                    int h = it->first;
                    if (h == 0) continue;
                    if (h > H) break;
                    while (!s.empty() && s.top().second < h) {
                        // must remove useless discrete values, else TLE
                        if (--d[s.top().second] <= 0) d.erase(s.top().second);
                        s.pop();
                    }
                    if (!s.empty()) {
                        ans += (i - s.top().first - 1) * (h - last);
                        //cout << i << " " << H << " at "<< h << " ans = " << ans << endl;
                    }
                    last = h;
                }
            }
            if (H > 0) s.push({i, H});
        }
        return ans;
    }
};

接雨水2D

仍然是贪心，1D中只求每个位置的左右最高点，在2D中变成了求每个位置到任意边界的所有路径中的最高点！（而不仅仅是四个方向的最高点）

于是这其实变成了Dijkstra最短路问题。

typedef pair<int,int> pii;

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {  
        if (heightMap.size() <= 2 || heightMap[0].size() <= 2) {
            return 0;
        }  
        int m = heightMap.size();
        int n = heightMap[0].size();
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        vector<vector<bool>> visit(m, vector<bool>(n, false));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    pq.push({heightMap[i][j], i * n + j});
                    visit[i][j] = true;
                }
            }
        }

        int res = 0;
        int dirs[] = {-1, 0, 1, 0, -1};
        while (!pq.empty()) {
            pii curr = pq.top();
            pq.pop();            
            for (int k = 0; k < 4; ++k) {
                int nx = curr.second / n + dirs[k];
                int ny = curr.second % n + dirs[k + 1];
                if( nx >= 0 && nx < m && ny >= 0 && ny < n && !visit[nx][ny]) {
                    if (heightMap[nx][ny] < curr.first) {
                        res += curr.first - heightMap[nx][ny]; 
                    }
                    visit[nx][ny] = true;
                    pq.push({max(heightMap[nx][ny], curr.first), nx * n + ny});
                }
            }
        }

        return res;
    }
};