题目描述

在一条生产线上，产品按照不同的质量进行排列，每个产品只能在同一方向上移动。当两个质量不同的产品相遇时，质量较低的产品将被移出生产线，如果产品质量相同，则两个产品均移除生产线。需要输出产品相遇的次数。

输入描述：

• 第 1 行输入一个正整数 n，表示产品数量，1 <= n <= 100000。
• 第 2 行是一个整数数组，描述每个产品的质量和移动方向，其中负数表示产品向左移动，正数表示产品向右移动。质量范围为 1~1000。

输出描述：

• 输出产品相遇的次数。

题解

思路

使用栈模拟向右移动的产品，遇到向左移动的产品时，执行碰撞规则：

1. 栈顶产品质量小于当前产品：移除栈顶，继续碰撞。
2. 栈顶产品质量等于当前产品：双方移除，停止碰撞。
3. 栈顶产品质量大于当前产品：当前产品移除，停止碰撞。
   每次碰撞计数加一。遍历结束后，输出相遇次数。

复杂度分析

• 时间复杂度：
  遍历一次数组，每个产品最多入栈和出栈一次，时间复杂度为 O(n)。

• 空间复杂度：
  栈的空间消耗为 O(n)（最坏情况下所有产品向右移动）。

代码实现

C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

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

    stack<int> st;
    int ans = 0;

    for (int i = 0; i < n; i++) {
        if (a[i] > 0) { 
            // 向右移动的产品入栈
            st.push(a[i]);
        } else { 
            // 遇到向左移动的产品
            while (!st.empty()) {
                ans++; // 相遇计数
                if (st.top() == -a[i]) { 
                    // 质量相等，双方移除
                    st.pop();
                    break;
                } else if (st.top() > -a[i]) { 
                    // 栈顶质量更大，当前产品被移除
                    break;
                } else { 
                    // 栈顶质量更小，移除栈顶
                    st.pop();
                }
            }
        }
    }

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

Java

import java.util.*;

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

        Stack<Integer> stack = new Stack<>();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            if (a[i] > 0) { 
                // 向右移动的产品入栈
                stack.push(a[i]);
            } else { 
                // 遇到向左移动的产品
                while (!stack.isEmpty()) {
                    ans++; // 相遇计数
                    if (stack.peek() == -a[i]) { 
                        // 质量相等，双方移除
                        stack.pop();
                        break;
                    } else if (stack.peek() > -a[i]) { 
                        // 栈顶质量更大，当前产品被移除
                        break;
                    } else { 
                        // 栈顶质量更小，移除栈顶
                        stack.pop();
                    }
                }
            }
        }

        System.out.println(ans);
    }
}

Python

def product_collisions(n, products):
    stack = []
    ans = 0

    for product in products:
        if product > 0:
            # 向右移动的产品入栈
            stack.append(product)
        else:
            # 遇到向左移动的产品
            while stack:
                ans += 1  # 相遇计数
                if stack[-1] == -product:
                    # 质量相等，双方移除
                    stack.pop()
                    break
                elif stack[-1] > -product:
                    # 栈顶质量更大，当前产品被移除
                    break
                else:
                    # 栈顶质量更小，移除栈顶
                    stack.pop()

    return ans

# 输入
n = int(input())
products = list(map(int, input().split()))

# 输出结果
print(product_collisions(n, products))

题目内容

在一条生产线上，产品按照不同的质量进行排列，每个产品只能在同一方向上移动。当两个质量不同的产品相遇时，质量较低的产品将被移出生产线，如果产品质量相同，则$2$个产品均移除生产线，输出产品相遇的次数。产品的移动速度都一样，注意一下解题的性能。

输入描述

第$1$行输入一个正整数$n$，表示产品数量,$1<=n<=100000$

第$2$行是一个整数数组，描述每个产品的质量和移动方向，其中负数表示产品向左移动，正数表示产品向右移动。产品的质量范围为$1$~$1000$

不用考虑非法输入，用例保证输入合法性

输出描述

产品相遇的次数

样例1

输入

3
4 88 -4

输出

1 

说明

示例中有$3$个产品，质量分别为$4,88,4$，其中前$2$个产品向右生产线的右边移动，第$3$个产品向生产线的左边移动，第$2$个产品和第$3$个产品相遇时，第$2$个产品质量更大，第$3$个产品被移出生产线，移除后生下$2$个产品均向右移动，质量分别是$4,88$，因为方向和速度都一样不会相遇，所以产品相遇次数是$1$

样例2

输入

2
15 -5

输出

1

说明

示例中有$2$个产品,质量分别是$15,5$，第$1$个产品向生产线的右边移动，第$2$个产品向生产线的左边移动，$2$个产品在相遇时第一个产品的质量大于第$2$个产品，所以第$2$个产品被移出生产线，移除后生产线上只剩第$1$个产品，质量是$15$，向右移动，不会再有产与之相遇，所以产品相遇次数是$1$

样例3

输入

4
10 5 -5 -15

输出

2

说明

示例中有$4$个产品,质量分别是$10,5,5,15,$第$1$个产品向右移动，第$2$个产品向生产线的右边移动，第$3$个产品向生产线的左边移动，第$4$个产品向左移动，由于产品移动的速度一样，第$2$个和第$3$个产品会先相遇，$2$个产品在相遇时$2$个产品的质量相同，所以$2$个产品均被移除，移除后剩余第$1$个和第$4$个产品，一个往右移 动，一个往左移动，所以他们也会相遇，相遇后移除质量小的第$1$个产品，生产线只剩下第$4$个产品向左移动