Dãy con min max

View as PDF

Points: 300 (p) Time limit: 1.0s Memory limit: 977M Input: stdin Output: stdout

Cho một dãy gồm \(n\) số nguyên \(A=(a_1,a_2,…,a_n)\). Ta định nghĩa: đoạn con của dãy \(A\) là một dãy các phần tử liên tiếp nhau thuộc \(A\). Hoặc có thể viết \((a_i,a_{i+1},…,a_j)\) là một đoạn con của \(A\) với \(i \leq j\). Độ dài của đoạn con được tính là số phần tử của đoạn con đó, ví dụ, đoạn con trên có độ dài là \(j-i+1\).

Yêu cầu: Tìm một đoạn con có độ dài ngắn nhất chứa cả số lớn nhất và số nhỏ nhất của dãy \(A\).

Input

  • Dòng đầu chứa số nguyên dương \(n \ (1 \leq n \leq 10^5)\).
  • Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,….,a_n\).

Output

  • Một số duy nhất là độ dài của đoạn con tìm được thỏa mãn yêu cầu đề bài.

Example

Test 1

Input
8
1 3 6 2 8 1 3 8 
Output
2

Comments


  • 1
    penistone    3:02 p.m. 21 nov, 2023

    Gợi ý
    Sau khi tìm đc min và max, ta có vector<int> vfirst,vsecond với vfirst là vị trí của max, min và vsecond là giá trị max,min. Sau đó khi duyệt mảng vsecond xét nếu vsecond[i] khác vsecond[i+1] thì ta cập nhật min khoảng cách (vì các chỉ số đã được sắp xếp nên khi vsecond[i]!=vsecond[i+1] thì 2 phần tử max, min liền kề nhau nên chỉ việc cập nhật min khoảng cách)
    Code C++/C++14: https://ideone.com/vad71D

    • 1 more comment