网页设计一页多少钱_珠海市网站建设品牌_爱站工具包下载_百度软文推广怎样收费

• 暴力解法：
  • 遍历每根柱子，对每根柱再遍历右边比其高手柱子，和左边比其高的柱子，根据凹槽深度来求解容量
  • 优化：预处理，即先存每根柱子右边比其高的柱子是哪一个到第一个数组，再用另一个数组来存其左边比其高的柱子是哪一个
• 单调栈：题目比较类似每日温度
  • 这道题是要找三个元素的位置
    • 第一个元素就是遍历中的元素，用当前遍历的下标值来确定
    • 第二个元素就是第一个右边比其大的元素，这个就是要满足条件即将压入栈中的元素
    • 第三个元素就是第一个左边比其大的元素，这个元素就在栈中紧跟着要出栈的元素
  • 这个栈的作用是什么（补充知识点）
    • 之前遍历过的元素
    • 只有这样，当前遍历的元素才可能是栈中元素右边第一个比其（栈顶元素）大的元素
  • 这道题对栈顶元素与当前遍历元素值相等的情况，我选择不处理，直接跳到下一个元素

class Solution {
public:int trap(std::vector<int>& heights) {int len = heights.size(), sum = 0;if (len <= 2) {return 0;}std::stack<int> heights_indices;heights_indices.push(0);for (int i = 1; i < len; ++i) {if (heights[i] < heights[heights_indices.top()]) {heights_indices.push(i);} else if (heights[i] > heights[heights_indices.top()]) {while (!heights_indices.empty() && heights[i] > heights[heights_indices.top()]) {int bottom_index = heights_indices.top();heights_indices.pop();if (!heights_indices.empty()) {int min_height = std::min(heights[i], heights[heights_indices.top()]);sum += (min_height - heights[bottom_index]) * (i - heights_indices.top() - 1);}}heights_indices.push(i);}}return sum;}
};

• 汇总