Neo's Blog

int q[N];
int hh = 0;
int tt = -1;
//push
q[++tt] = x;
//pop
q[hh++];
//is empty
hh > tt;

for (int i = 0; i < n; ++i) {
    while (tt >= hh && check_out(q[hh])) hh++; //判断是否滑出窗口
    while (tt >= hh && check(q[tt])) tt--;
    q[++tt] = i;
}

 class MaxQueue {
public:
    MaxQueue() {
        memset(q, 0, sizeof(q));
        hh = 0;
        tt = -1;
    }
    
    int max_value() {
        if (dq.size()) return q[dq.front()];
        else return -1;
    }
    
    void push_back(int value) {
        q[++tt] = value;
        //if (dq.size() && value >= q[dq.front()]) dq.clear();
        while (dq.size() && value > q[dq.back()]) dq.pop_back();
        dq.push_back(tt);
    }
    
    int pop_front() {
       if (tt < hh) return -1;

       //当前的hh
       if (dq.size() && dq.front() == hh) {
           dq.pop_front();
       }

       return q[hh++];
    }

private:
    int q[10010];
    int hh; //队头
    int tt; //队尾
    std::deque<int> dq;
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

int largestRectangleArea(vector<int>& heights) {
    int n = height.size();
    int res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; j++) {
            int minv = INF;
            for (int k = i; k <= j; ++k) {
                minv = min(minv, height[k]);
            }
            res = max(res, (i - j + 1) * minv);
        }
    }
    return res;
}

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> s(heights.size() + 2);
        vector<int> w(heights.size() + 2);
        int p = 0;

        heights.push_back(0);
        int res = 0;
        for (int i = 0; i < heights.size(); ++i) {
            if (heights[i] > s[p]) {
                s[++p] = heights[i];
                w[p] = 1;
            }
            else {
                int width= 0;
                while (s[p] > heights[i]) {
                    width += w[p];
                    res = max(res, width * s[p]);
                    p--;
                }
                s[++p] = heights[i];
                w[p] = width + 1;
            }
        }
        return res;
    }
};vf

public class Solution {
    public int calculateArea(int[] heights, int start, int end) {
        if (start > end)
            return 0;
        int minindex = start;
        for (int i = start; i <= end; i++)
            if (heights[minindex] > heights[i])
                minindex = i;
        return Math.max(heights[minindex] * (end - start + 1), Math.max(calculateArea(heights, start, minindex - 1), calculateArea(heights, minindex + 1, end)));
    }
    public int largestRectangleArea(int[] heights) {
        return calculateArea(heights, 0, heights.length - 1);
    }
}

int largestRectangleArea(vector<int>& heights) {
    int n = height.size();
    int res = 0;
    for (int i = 0; i < n; ++i) {
        int minv = height[i];
        for (int j = i; j < n; j++) { //确保j从小变大
            int minv = INF;
            //如果i看作一个定值，下面这个循环，其实每次都做了相同的工作，重复扫描[i, j]
            //所以可以做累计处理
            //for (int k = i; k <= j; ++k) {
            //    minv = min(minv, height[k]);
            //}
            minv = min(minv, height[j]);
            res = max(res, (i - j + 1) * minv);
        }
    }
    return res;
}

int dfs(vector<int>& height, int l, int r) {
    int p = find_min(height, l, r);

    int left_lower = 0； //往左查找，直到找到比height[p]更小的元素
    int right_lower = 0；//往右查找，直到找到比height[p]更小的元素

    return max(dfs(l, p - 1), dfs(p + 1, r), height[p] * (right_lower - left_lower);
}

int largestRectangleArea(vector<int>& height) {
  return dfs(height, 0, height.size() - 1);
}

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

        return res;
    }
};

int trap(vector<int>& height) {
    int n = height.size();
    int res = 0;
    for (int i = 1; i < n; ++i) {

        //往左找到最大值
        int lmax = 0;
        for (int j = 0; j < i; ++j) {
            lmax = max(lmax, height[j]);
        }

        //往右找到最大值
        int rmax = 0;
        for (int j = i + 1; j < i; ++j) {
            rmax = max(rmax, height[j]);
        }

        res += min(rmax, lmax) - height[i];

    }
}

int trap(vector<int>& height) {
    int n = height.size();
    int res = 0;
    int lmax[N], rmax[N];
    //正序遍历
    for (int i = 1; i < n; ++i) {
        lmax[i] = max(lmax[i - 1], height[i - 1]);
    }

    //倒序遍历 
    for (int i = n; i >= 0; --i) {
        rmax[i] = max(rmax[i + 1], height[i + 1]);
    }

    for (int i = 1; i < n; ++i) {
        res += min(lmax[i], rmax[i]) - height[i];
    }
}

int trap(vector<int>& height) {
    int n = height.size();
    int res = 0;
    int lmax, rmax;
    int i = 1, j = n - 2;

    while (i < j) {
        lmax = max(lmax, height[i - 1]);
        rmax = max(rmax, height[j + 1]);
        if (lmax < rmax) {
            res += lmax - height[i];
            i++;
        }
        else {
            res += rmax - height[j];
            j--;
        }
    }
    return res;
}

class Solution {
public:
    int trap(vector<int>& height) {
        int lmax = 0, rmax = 0;
        int l = 0, r = height.size() - 1;
        int sum = 0;

        while (l <= r) {
            for (; l <= r && (lmax = max(height[l], lmax)) <= rmax; ++l) {
                sum += lmax - height[l];
            }
            for (; r >= l && (rmax = max(height[r], rmax)) <= lmax; r--) {
                sum += rmax - height[r];
            }
        } 

        return sum;
    }
};

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        stack<int> s;
        s.push(-1);
        int res = 0;
        for (int i = 0; i < arr.size(); ++i) {
            while (s.top() != -1 && arr[s.top()] < arr[i]) {
                int cur = s.top(); //当前计算的格子
                s.pop();
                int left = s.top();
                if (left >= 0) {
                    res += (min(arr[left], arr[i]) - arr[cur]) * (i - left - 1);
                    //cout << "i:" << i << ", cur:"  << cur << ", res: " << res << endl;
                }
            }

            s.push(i);
        }

        return res;
    }
};

int prefix_sum() {
    S[i] = a[1] + a[2] + ... a[i];
    a[l] + ... + a[r] = S[r] - S[l - 1];
}

int 2d_preifx_sum()
{
    S[i, j] = 第i行j列格子左上部分所有元素的和
    //以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
    S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
}

B[l] += c, B[r + 1] -= c

S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

//滑动窗口 模版
for (int i = 0, j = 0; i < n; i ++ )
{
    //i是新进入窗口的元素
    //[j,i]是窗口边缘，j是要滑出的下标，i是新进入的下标
    while (j < i && check(i, j)) j ++ ; //j是可能要滑出窗口的元素

    // 具体问题的逻辑
}

int i = 0, j = 0, n;
while (i < n) {
    //对新进入窗口的元素i进行处理

    while (j < i && check(xx)) {
        //对出窗口的元素j进行处理
        j++;
    }
}

int longestSubstringWithoutDuplication(string s) {
      int i, j = 0, n =s.size();
      unordered_map<char,int> counter;
      int res = 0;
      while (i < n) {
          char c = s[i];
          counter[c]++;
          if (counter[c] == 1) { //新来了一个不重复元素，则窗口扩大了
               res = max(res, i - j + 1)
          }
          i++;
          while (j < i && counter[c] > 1) { //如果现在窗口已经不在符合条件，则一直往前移动left，直到窗口重新满足
              counter[s[j]]--;
              j++;
          }
      }
   }

class Solution {
public:
    int maxLength(vector<int>& arr) {
        unordered_map<int, int> counter;

        int i = 0, j = 0, res = 0;
        while (j < arr.size()) {
            counter[arr[j]]++;
            while (counter[arr[j]] > 1) {
                counter[arr[i++]]--;
            }

            res = max(j - i + 1, res);
            j++;
        }

        return res;
    }
};

class Solution {
public:
    unordered_map<char, int> pattern;

    string minWindow(string src, string tt) {
        //将目标串转换为方便检查处理的hashmap
        for (auto x : tt) {
            pattern[x]++;
        }
        int cnt = pattern.size();

        string res;
        for (int i = 0, j = 0, c = 0; i < src.size(); ++i) {
            if (pattern[src[i]] == 1 ) c++;
            pattern[src[i]]--; //将src[i]标记为缺少状态
            //满足了，并且某一个字符是缺的【非pattern中的字符一定缺；并且一定会被补上】，则往前移动
            while (c == cnt && pattern[src[j]] < 0) {
                pattern[src[j++]]++; 
            } 
            if (c == cnt) {
                if (res.empty() || res.size() > i - j + 1) res = src.substr(j, i - j + 1);
            }
        }
        return res;
    }
};