CSES - Nearest Smaller Values - LQDOJ: Le Quy Don Online Judge

CSES - Nearest Smaller Values

Authors:

Problem types

Points: 1100 Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

Given an array of \(n\) integers, your task is to find for each array position the nearest position to its left having a smaller value.

Input

The first input line has an integer \(n\): the size of the array.
The second line has \(n\) integers \(x_1,x_2,\ldots,x_n\): the array values.

Output

Print \(n\) integers: for each array position the nearest position with a smaller value. If there is no such position, print \(0\).

Constraints

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

Example

Sample input

8
2 5 1 4 8 3 2 5

Sample output

0 1 0 3 4 3 3 7

Comments

NEYAKO • 7:46 a.m. 6 mar, 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?

0
Reply Share

quangchinhtran • 10:56 a.m. 18 jul, 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
-1
Reply Share

1 reply

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);
    }
}

-1

1 reply