CSES - Nearest Smaller Values | Giá trị nhỏ hơn gần nhất

Xem PDF

Điểm: 1100 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là với mỗi vị trí của mảng, tìm vị trí gần nhất bên trái của nó mà có giá trị nhỏ hơn.

Input

  • Dòng đầu vào đầu tiên có một số nguyên \(n\): kích thước của mảng.
  • Dòng thứ hai có n số nguyên \(x_1,x_2,\ldots,x_n\): các giá trị của mảng.

Output

  • In \(n\) số nguyên: vị trí gần nhất nhỏ hơn cho mỗi vị trí trong mảng. Nếu không có, in \(0\).

Constraints

  • \(1 \leq n \leq 2 \cdot 10 ^ 5\)
  • \(1 \leq x_i \leq 10 ^ 9\)

Example

Sample input

8
2 5 1 4 8 3 2 5

Sample output

0 1 0 3 4 3 3 7


Bình luận

  • NEYAKO 7:46 a.m. 6 Tháng 3, 2025

    cho mình hỏi là mấy bro gửi code này có bị ban ko hay là những người chép code mới bị ban?

    • quangchinhtran 10:56 a.m. 18 Tháng 7, 2024

      def find_nearest_smaller_left(n, arr):
      stack = []
      result = [0] * n

      for i in range(n):
          while stack and arr[stack[-1]] >= arr[i]:
              stack.pop()
      
          if stack:
              result[i] = stack[-1] + 1  # Chuyển từ 0-based index sang 1-based index
          else:
              result[i] = 0
      
          stack.append(i)
      
      return result
      

      Đọc input

      n = int(input().strip())
      arr = list(map(int, input().strip().split()))

      Tìm vị trí gần nhất bên trái có giá trị nhỏ hơn

      result = find_nearest_smaller_left(n, arr)

      print(" ".join(map(str, result)))
      python 3 100% AC

      • bienkhoatinh 4:44 p.m. 12 Tháng 5, 2024 đã chỉnh sửa

        solution theo stack cho ae tham khảo

        #include <bits/stdc++.h>
        using namespace std;
        const int N = 1e6 + 6;
        int n, a[N];
        stack <int> s;
        int main() {
            ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
        
            cin >> n;
            for (int i = 1; i <= n; i++)
                cin >> a[i];
        
            for (int i = 1; i <= n; i++) {
                while (!s.empty() && a[s.top()] >= a[i]) {
                    s.pop();
                }
                if (!s.empty())
                    cout << s.top() << " ";
                else cout << 0 << " ";
                s.push(i);
            }
        }