结队编程 - 华为OD统一考试（D卷）

OD统一考试（D卷）

分值： 200分

题解： Java / Python / C++

题目描述

某部门计划通过结队编程来进行项目开发，已知该部门有 N 名员工，每个员工有独一无二的职级，每三个员工形成一个小组进行结队编程，结队分组规则如下：

从部门中选出序号分别为 i、j、k 的3名员工，他们的职级分别为 level[i]，level[j]，level[k]，结队小组满足 level[i] < level[j] < level[k] 或者 level[i] > level[j] > level[k]，其中 0 ≤ i < j < k < n。

请你按上述条件计算可能组合的小组数量。同一员工可以参加多个小组。

输入描述

第一行输入：员工总数 n

第二行输入：按序号依次排列的员工的职级 level，中间用空格隔开

备注：

1 <= n <= 6000

1 <= level[i] <= 10^5

输出描述

可能结队的小组数量

示例1

输入：
4
1 2 3 4

输出：
4

说明：
可能结队成的组合(1,2,3)、(1,2,4)、(1,3,4)、(2,3,4)

示例2

输入：
3
5 4 7

输出：
0

说明：
根据结队条件，我们无法为该部门组建小组

题解

这个问题可以通过使用单调栈来优化组合计算。

具体来说，我们可以分别利用两个单调栈来维护每个员工左侧和右侧的符合条件的员工数量，从而避免三重循环带来的高时间复杂度。

算法步骤

1. 预处理左侧数据：

   • 使用两个单调栈分别计算每个员工左侧大于和小于当前职级的员工数量。

2. 预处理右侧数据：

   • 使用两个单调栈分别计算每个员工右侧大于和小于当前职级的员工数量。

3. 计算满足条件的组合数量：

   • 使用预处理得到的左侧和右侧的数据，计算符合条件的组合数量。

时间复杂度： O(n)。

Java

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] levels = new int[n];
        for (int i = 0; i < n; i++) {
            levels[i] = scanner.nextInt();
        }

        int[] gt = new int[n];  // 左侧小于当前职级的员工数量
        int[] lt = new int[n];  // 左侧大于当前职级的员工数量

        Stack<Integer> maxStack = new Stack<>();
        Stack<Integer> minStack = new Stack<>();

        // 计算左侧数据
        for (int i = 0; i < n; i++) {
            while (!maxStack.isEmpty() && levels[i] >= levels[maxStack.peek()]) {
                maxStack.pop();
            }
            lt[i] = maxStack.size();

            while (!minStack.isEmpty() && levels[i] <= levels[minStack.peek()]) {
                minStack.pop();
            }
            gt[i] = minStack.size();

            maxStack.push(i);
            minStack.push(i);
        }

        long ans = 0;
        maxStack.clear();
        minStack.clear();

        // 计算右侧数据并统计结果
        for (int i = n - 1; i >= 0; i--) {
            while (!maxStack.isEmpty() && levels[i] >= levels[maxStack.peek()]) {
                maxStack.pop();
            }
            ans += (long) maxStack.size() * gt[i];

            while (!minStack.isEmpty() && levels[i] <= levels[minStack.peek()]) {
                minStack.pop();
            }
            ans += (long) minStack.size() * lt[i];

            maxStack.push(i);
            minStack.push(i);
        }

        System.out.println(ans);
    }
}

Python

n = int(input())
level = list(map(int, input().split()))

max_stack, min_stack = [], []
gt, lt = [0] * n, [0]*n

# 计算左侧数据
for i, v in enumerate(level):
    while max_stack and v >= max_stack[-1]:
        max_stack.pop()
    lt[i] = len(max_stack)

    while min_stack and v <= min_stack[-1]:
        min_stack.pop()
    gt[i] = len(min_stack)

    max_stack.append(v)
    min_stack.append(v)


ans = 0
max_stack, min_stack = [], []
# 计算右侧数据并统计结果
for i in range(n-1, -1, -1):
    v = level[i]
    while max_stack and v >= max_stack[-1]:
        max_stack.pop()
    ans += len(max_stack) * gt[i]

    while min_stack and v <= min_stack[-1]:
        min_stack.pop()
    ans += len(min_stack) * lt[i]

    max_stack.append(level[i])
    min_stack.append(level[i])


print(ans)

C++

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> level(n);
    for (int i = 0; i < n; ++i) {
        cin >> level[i];
    }

    vector<int> gt(n, 0), lt(n, 0);
    stack<int> maxStack, minStack;

    // 计算左侧数据
    for (int i = 0; i < n; ++i) {
        while (!maxStack.empty() && level[i] >= level[maxStack.top()]) {
            maxStack.pop();
        }
        lt[i] = maxStack.size();

        while (!minStack.empty() && level[i] <= level[minStack.top()]) {
            minStack.pop();
        }
        gt[i] = minStack.size();

        maxStack.push(i);
        minStack.push(i);
    }

    long long ans = 0;
    while (!maxStack.empty()) maxStack.pop();
    while (!minStack.empty()) minStack.pop();

    // 计算右侧数据并统计结果
    for (int i = n - 1; i >= 0; --i) {
        while (!maxStack.empty() && level[i] >= level[maxStack.top()]) {
            maxStack.pop();
        }
        ans += static_cast<long long>(maxStack.size()) * gt[i];

        while (!minStack.empty() && level[i] <= level[minStack.top()]) {
            minStack.pop();
        }
        ans += static_cast<long long>(minStack.size()) * lt[i];

        maxStack.push(i);
        minStack.push(i);
    }

    cout << ans << endl;
    return 0;
}

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏