`
SunnyYoona
  • 浏览: 361526 次
社区版块
存档分类
最新评论

LeetCode之Trapping Rain Water

 
阅读更多

【题目】

Givennnon-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given[0,1,0,2,1,0,1,3,2,1,2,1], return6.


The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.Thanks Marcosfor contributing this image!


【题意】

给定n个非负整数,代表一个柱状图,每一个柱子的宽度为1,计算下雨之后柱状图能装多少水?

例如:

[0,1,0,2,1,0,1,3,2,1,2,1] 返回 6

上述柱状图是由数组表示[0,1,0,2,1,0,1,3,2,1,2,1]。在这种情况下,6个单位的雨水(蓝色部分)被

【分析】

对于每个柱子,找到其左右两边最高的柱子,该柱子能容纳的面积就是 min(leftMostHeight,rightMostHeight) - height。所以,

1. 从左往右扫描一遍,对于每个柱子,求取左边最大值;

2. 从右往左扫描一遍,对于每个柱子,求最大右值;

3. 再扫描一遍,把每个柱子的面积并累加。

也可以,

1. 扫描一遍,找到最高的柱子,这个柱子将数组分为两半;

2. 处理左边一半;

3. 处理右边一半。

【代码】

/*********************************
*   日期:2014-01-20
*   作者:SJF0115
*   题号: Trapping Rain Water
*   来源:http://oj.leetcode.com/problems/trapping-rain-water/
*   结果:AC
*   来源:LeetCode
*   总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <malloc.h>
using namespace std;

class Solution {
public:
    int trap(int A[], int n) {
        if(A == NULL || n < 1)return 0;
        int i;

		int* leftMostHeight = (int*)malloc(sizeof(int)*n);
		int* rightMostHeight = (int*)malloc(sizeof(int)*n);

		int maxHeight = 0;
		for(i = 0; i < n;i++){
			leftMostHeight[i] = maxHeight;
			if(maxHeight < A[i]){
                maxHeight = A[i];
            }
		}

		maxHeight = 0;
		for(i = n-1;i >= 0;i--){
			rightMostHeight[i] = maxHeight;
			if(maxHeight < A[i]){
                maxHeight = A[i];
            }
		}

		int water = 0;
		for(i =0; i < n; i++){
			int curWater = min(leftMostHeight[i],rightMostHeight[i]) - A[i];
			if(curWater > 0){
				water += curWater;
			}
		}
		return water;
    }
};
int main() {
    Solution solution;
    int result;
    int A[] = {0,1,0,2,1,0,1,3,2,1,2,1};
    result = solution.trap(A,12);
    cout<<result<<endl;
    return 0;
}





【代码2】

class Solution {
public:
    int trap(int A[], int n) {
        int *max_left = new int[n]();
        int *max_right = new int[n]();
        for (int i = 1; i < n; i++) {
            max_left[i] = max(max_left[i - 1], A[i - 1]);
            max_right[n - 1 - i] = max(max_right[n - i], A[n - i]);
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int height = min(max_left[i], max_right[i]);
            if (height > A[i]) {
                sum += height - A[i];
            }
        }
        delete[] max_left;
        delete[] max_right;
        return sum;
    }
};


【代码3】

思路2

class Solution {
public:
    //时间复杂度 O(n),空间复杂度 O(1)
    int trap(int A[], int n) {
        // 最高的柱子,将数组分为两半
        int max = 0;
        for (int i = 0; i < n; i++){
            if (A[i] > A[max]) max = i;
        }
        int water = 0;
        for (int i = 0, leftMaxHeight = 0; i < max; i++){
            if (A[i] > leftMaxHeight){
                leftMaxHeight = A[i];
            }
            else {
                water += leftMaxHeight - A[i];
            }
        }
        for (int i = n - 1, rightMaxHeight = 0; i > max; i--){
            if (A[i] > rightMaxHeight){
                rightMaxHeight = A[i];
            }
            else{
                water += rightMaxHeight - A[i];
            }
        }
        return water;
    }
};

【代码4】

//第4种解法,用一个栈辅助,小于栈顶的元素压入,大于等于栈顶就把栈里所有小于或等于当
//前值的元素全部出栈处理掉。
// LeetCode, Trapping Rain Water
// 用一个栈辅助,小于栈顶的元素压入,大于等于栈顶就把栈里所有小于或
// 等于当前值的元素全部出栈处理掉,计算面积,最后把当前元素入栈
// 时间复杂度 O(n),空间复杂度 O(n)
class Solution {
public:
    int trap(int a[], int n) {
        stack<pair<int, int>> s;
        int water = 0;
        for (int i = 0; i < n; ++i) {
            int height = 0;
            // 将栈里比当前元素矮或等高的元素全部处理掉
            while (!s.empty()) {
                int bar = s.top().first;
                int pos = s.top().second;
                // bar, height, a[i] 三者夹成的凹陷
                water += (min(bar, a[i]) - height) * (i - pos - 1);
                height = bar;
                if (a[i] < bar) // 碰到了比当前元素高的,跳出循环
                    break;
                else
                s.pop(); // 弹出栈顶,因为该元素处理完了,不再需要了
            }
            s.push(make_pair(a[i], i));
        }
        return water;
    }
};


类似题目:

庞果网之寻找直方图中面积最大的矩形

[LeetCode]11.Container With Most Water


分享到:
评论

相关推荐

    javalruleetcode-LeetCode:LeetCode算法问题

    Trapping Rain Water LeetCode 61 RotateList LeetCode 75 Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels...

    leetcode卡-LeetCode:我的LeetCode解决方案

    Trapping Rain Water II], BFS/Priority queue 2017.06.19 打卡[LeetCode 145. Binary Tree Postorder Traversal], Tree/stack 2017.06.20 打卡[LeetCode 107. Binary Tree Level Order Traversal II], Tree/BFS ...

    leetcode1004-leetcode:leetcode删号重练个人记录:)

    leetcode 1004 leetcode NEXT:42 Trapping Rain Water 刷题顺序 刷题内容总的来说包括数据结构、算法和技巧 按照tag分类别进行刷题,跳过like&lt;200&gt;like的题目 按Acceptance由高到低进行,每个tag所刷题目大于20...

    erlang入门级练习:LeetCode OJ问题的部分erlang 源码

    我自己在新学erlang,在LeetCode OJ上找了题目练习,题目很适合新手... "three_sum.erl","trapping_rain_water.erl", "valid_palindrome.erl" 个人认为dungeon_game这个题目解题逻辑很体现erlang的函数式的思维逻辑

    Leetcode-Solutions:JavaScript 语言的 Leetcode 解决方案

    力码解决方案 Leetcode是一个网站,人们——...├── Trapping Rain Water │ ├── Readme.md │ └── solution.js ├── Wildcard Matching │ ├── Readme.md │ └── solution.js ├── Valid Number │

    lrucacheleetcode-leetcode:leetcode

    Trapping Rain Water 85. Maximal Rectangle Monotonic stack for 2d array 239. Sliding Window Maximum 255. Verify Preorder Sequence in Binary Search Tree 907. Sum of Subarray Minimums 二叉搜索树 99. ...

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...

    leetcode添加元素使和等于-leetcode:我的leetcode解决方案

    leetcode添加元素使和等于 经验教训 一定要吧功能尽量细化为函数,这样一者做题思路比较清晰,二者可以在某些情况下直接return值。 如果输入的形式是一个序列,则可以想想:分治、动规、贪婪,一般不建议搜索,因为...

    多线程leetcode-leetcode-java:leetcode上的题解,基于java语言

    多线程 leetcode 前言 每天刷点leetcode,基于java语言实现。 leetcode上难度分三档:easy,medium,hard. 如下: easy medium Remove Nth Node From End of List Swap Nodes ...Trapping Rain Water

    leetcode不会-3D-Trapping-Rain-Water-System:该repo包含复杂3D雨水收集系统的解决方案,该系统在Lee

    leetcode 不会3D 捕集雨水系统 该 repo 包含复杂 3D 雨水收集系统的解决方案,该系统在 Leetcode Problem No. 407 和 Google Interview Round 中提出。 此外,它将“0”视为系统的排水。 (查看自述文件以获得详细...

    leetcode跳跃-leetcode:leetcode解题之路

    接雨水](./Array/trapping-rain-water.md) [0048 旋转图像](./Array/rotate-image.md) Heap 堆 [0023 合并K个排序链表](./Heap/merge-k-sorted-lists.md) String 字符串 [0006 Z字形变换](./String/zigzag-...

    leetcode答案-Algorithms:算法

    leetcode 答案 Algorithms 一、three sum 三数相加问题 问题描述 在一个由 number 组成的数组中,找到所有的 3 个数组成的数组,使得这三个数字的和等于给定的数字 解答 考虑到时间复杂度肯定大于等于 O(n²) 可以先...

    leetcode答案-leetcode:leetcode.com问题的答案

    leetcode 答案leetcode leetcode.com 问题的答案 跑步 python -m venv .venv source .venv/bin/activate pip install -r requirements.txt pytest &lt;question&gt;/tests.py ...lc42_trapping_rain_water/tests.py

    leetcode添加元素使和等于-leetcode:力码

    trapping-rain-water 滑动窗口 通过窗口的大小不断调整来找到合适的值,或者窗口大小不变,通过左右移动来找到相应的结果 \ \ 其他 非 LeetCode 题,单纯在别人面试中看到的 \ 链表 \ swap-nodes-in-pairs linked-...

    收集面试中提出的一些重要问题。-C/C++开发

    收集面试中提出的一些重要问题。 数据结构算法面试问题面试中提出的一些重要问题的集合。...数组https://leetcode.com/problems/3sum/ [解决方案] https://leetcode.com/problems/trapping-rain-water/ [解决方案] ...

    cpp-算法精粹

    Trapping Rain Water Rotate Image Plus One Climbing Stairs Set Matrix Zeroes Gas Station Candy Majority Element Rotate Array Contains Duplicate Contains Duplicate II Contains Duplicate III Product of ...

Global site tag (gtag.js) - Google Analytics