木板接水

#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main(){
    int T = 0;
    while (cin >> T)
    {
        vector<vector<int>> input;
        vector<int> ans;
        for (int i = 0; i < T; i++)
        {
            int n = 0;
            cin >> n;
            vector<int> temp(n,0);
            for (int index = 0; index < n; index++)
            {
                cin >> temp[index];
            }
            input.push_back(temp);
        }

        for (int i = 0; i < input.size(); i++)
        {
            vector<int> dp(input[i].size(),0);
            for (int j = 1; j < input[i].size(); j++)
            {
                if (input[i][j] <= input[i][j - 1])
                {
                    dp[j] = dp[j - 1] + input[i][j];
                }
                else{
                    int indexJ = j - 1;
                    int max_index = j - 1;
                    for (; indexJ >= 0; indexJ--)
                    {
                        if (input[i][indexJ] >= input[i][max_index])
                        {
                            max_index = indexJ;
                        }
                        if (input[i][j] < input[i][indexJ])
                        {
                            break;
                        }
                    }
                    if (indexJ == -1)
                    {
                        dp[j] = dp[max_index] + (j - max_index)*input[i][max_index];
                    }
                    else{
                        dp[j] = dp[indexJ] + (j - indexJ)*input[i][j];
                    }

                }
            }
            ans.push_back(dp.back());
        }
        for (auto &c : ans)
        {
            cout << c << endl;
        }
    }
    return 0;
}

[编程题]木板接水
这道题与leetcode上的接雨水非常类似，双指针解法尤其适合这道题。

package main

import (
    "fmt"
)

func getVolume(board []int) (ans int) {
    //左边的最高挡板的位置，右边的最高挡板的位置
    l,r:=0, len(board)-1
    //左边的最高挡板的高度，右边的最高挡板的高度
    lm,rm:=board[l],board[r]
    for l<r{
        //较短的挡板决定水位
        if board[l]<board[r]{
            //如果当前挡板比左短板更短则更新左短板
            if board[l]>lm{
                lm=board[l]
            }
            //加入结果
            ans+=lm
            l++
        }else{
            //如果当前挡板比右短板更短则更新右短板
            if board[r]>rm{
                rm=board[r]
            }
            //加入结果
            ans+=rm
            r--
        }
    }
    return ans
}

func main() {
    var t,n,h int
    fmt.Scan(&t)
    for i:=0;i<t;i++{
        fmt.Scan(&n)
        hs:=[]int{}
        for j:=0;j<n;j++{
            fmt.Scan(&h)
            hs = append(hs, h)
        }
        fmt.Println(getVolume(hs))
    }
}