LeetCode42.接雨水-创新互联

主页有其他数据结构内容（持续更新中）

创新互联公司是一家集网站建设,京口企业网站建设,京口品牌网站建设,网站定制,京口网站建设报价,网络营销,网络优化,京口网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。难度：Hard 代码：

class Solution {public:
    int trap(vector& height) {if (height.size()<= 2) return 0; // 可以不加
        stackst; // 存着下标，计算的时候用下标对应的柱子高度
        st.push(0);
        int sum = 0;
        for (int i = 1; i< height.size(); i++) {if (height[i]< height[st.top()]) { // 情况一
                st.push(i);
            } if (height[i] == height[st.top()]) {// 情况二
                st.pop(); // 其实这一句可以不加，效果是一样的，但处理相同的情况的思路却变了。
                st.push(i);
            } else {// 情况三
                while (!st.empty() && height[i] >height[st.top()]) {// 注意这里是while
                    int mid = st.top();
                    st.pop();
                    if (!st.empty()) {int h = min(height[st.top()], height[i]) - height[mid];
                        int w = i - st.top() - 1; // 注意减一，只求中间宽度
                        sum += h * w;
                    }
                }
                st.push(i);
            }
        }
        return sum;
    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享名称：LeetCode42.接雨水-创新互联
链接分享：http://6mz.cn/article/cejhch.html