Dãy con min max

Xem PDF

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 977M Input: bàn phím Output: màn hình

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

Bình luận


  • 1
    penistone 3:02 p.m. 21 Tháng 11, 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


    • 2
      Cao_Duy_Anh 10:06 p.m. 22 Tháng 8, 2023

      có thể tìm min,max của dãy rồi tìm vị trí của min và vị trí của max, sau đó đoạn con có độ dài ngắn nhất=abs(vtmax-vtmin)+1
      mình gợi ý vậy thôi :))
      vd:
      8
      1 3 6 2 8 1 3 8

      vị trí min tìm được là 6 ( tức là 1)
      vị trí max tìm được là 8 ( tức là 8)
      sau đó tìm độ dài đoạn con là min(res,(8-6)+1) = 2;