C/C++教程

接雨水C++

本文主要是介绍接雨水C++,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n; char c; int sum1=0; vector<int>x, a;//x存储数,a存储进栈的下标
        int maa;
    	while(scanf("%d",&n))
    	{
    		x.push_back(n);
    		c = getchar();
    		if (c == '\n')break;
    	}
    	vector<int> result(x);
    	for(int i=0;i<x.size();++i)
    	{
    		while (!a.empty()&&x[a.back()]<x[i])//单减;
    		{
                maa = 0;
                n = a.back();//记录位置
                a.pop_back();//此时栈顶为上一个比他大的数字位置;
                if (!empty(a))
                {
                    maa = min(x[a.back()], x[i]);
                    for (int j = a.back() + 1; j < i; ++j)x[j] = maa;
                }
                //if (empty(a))result[n] = i * x[n];
    		}
    		a.push_back(i);
    	}
    	//for (int i = 0; i < result.size(); ++i)cout << result[i]<<" ";
        for (int i = 0; i < result.size(); ++i)sum1+=(x[i]-result[i]);
        cout << sum1;
    	return 0;
    }//1 1 2 1 3 0 2 0 5 0 4 0 1 1 2:16

注意对单调栈的理解,即以O(n)的速度得知每个元素的左右各两边第一个比他(小)大的位置上;

这篇关于接雨水C++的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!