배열을 정렬하기 위해 제거할 가장 짧은 하위 배열
1574. 배열 정렬을 위해 제거할 최단 하위 배열
난이도:중
주제: 배열, 두 포인터, 이진 검색, 스택, 단조 스택
정수 배열 arr이 주어지면 arr의 나머지 요소가 감소하지 않도록.
arr에서 하위 배열(비어 있을 수 있음)을 제거합니다.제거할 가장 짧은 하위 배열의 길이를 반환합니다.
하위 배열은 배열의 연속된 하위 시퀀스입니다.
예 1:
- 입력: arr = [1,2,3,10,4,2,3,5]
- 출력: 3
-
설명: 제거할 수 있는 가장 짧은 하위 배열은 길이가 3인 [10,4,2]입니다. 그 뒤의 나머지 요소는 정렬된 [1,2,3,3,5]입니다.
- 또 다른 올바른 해결책은 하위 배열 [3,10,4]을 제거하는 것입니다.
예 2:
- 입력: arr = [5,4,3,2,1]
- 출력: 4
- 설명: 배열이 엄격하게 감소하므로 단일 요소만 유지할 수 있습니다. 따라서 길이가 4인 [5,4,3,2] 또는 [4,3,2,1] 하위 배열을 제거해야 합니다.
예 3:
- 입력: arr = [1,2,3]
- 출력: 0
- 설명: 배열이 이미 감소하지 않습니다. 어떤 요소도 제거할 필요가 없습니다.
제약조건:
- 1 <= arr.length <= 105
- 0 <= arr[i] <= 109
힌트:
- 핵심은 각각 첫 번째 요소로 시작하거나 마지막 요소로 끝나는 감소하지 않는 가장 긴 하위 배열을 찾는 것입니다.
- 일부 하위 배열을 제거한 후 결과는 정렬된 접두어와 정렬된 접미어의 연결입니다. 여기서 접두사의 마지막 요소는 접미사의 첫 번째 요소보다 작습니다.
해결책:
정렬 및 이진 검색 기술을 사용할 수 있습니다. 계획은 다음과 같습니다.
접근하다:
-
두 가지 지침 접근 방식:
- 먼저 감소하지 않는 가장 긴 접두사(왼쪽 포인터)를 식별합니다.
- 그런 다음 감소하지 않는 가장 긴 접미사(오른쪽 포인터)를 식별합니다.
- 이후에는 배열의 중간 부분을 고려하여 결합된 배열이 감소하지 않도록 제거할 하위 배열을 조정하여 이 두 하위 배열을 결합해 보세요.
-
단조 스택:
- 단조 스택을 사용하면 정렬된 방식으로 하위 배열 요소를 관리할 수 있습니다.
-
단계:
- 감소하지 않는 가장 긴 접두사를 찾습니다(왼쪽).
- 가장 긴 비감소 접미사를 찾아보세요(오른쪽).
- 유효한 조합을 형성할 수 있는 요소를 찾아 두 하위 배열을 병합해 보세요.
-
최적화:
- 이진 검색을 사용하여 제거할 가장 작은 하위 배열을 찾기 위한 병합 단계를 최적화하세요.
PHP에서 이 솔루션을 구현해 보겠습니다: 1574. 배열 정렬을 위해 제거할 최단 하위 배열
설명:
감소하지 않는 가장 긴 접두사 및 접미사:
- 접두사는 요소가 감소하지 않는 순서가 될 때까지 배열을 처음부터 순회하여 결정됩니다.
- 마찬가지로 접미사는 끝에서부터 순회하여 결정됩니다.
최소 초기 제거:
- 접두사 또는 접미사만 유지하여 제거 길이를 계산합니다.
접두사 및 접미사 병합:
- 접두사의 마지막 요소가 접미사의 첫 번째 요소보다 작거나 같도록 두 개의 포인터(접두사의 경우 i, 접미사의 경우 j)를 사용하여 제거할 가장 작은 하위 배열을 찾습니다.
반품 결과:
- 결과는 제거할 하위 배열의 최소 길이이며, 초기 제거 길이나 접두사와 접미사 병합 길이 중 더 작은 길이로 계산됩니다.
복잡성
- 시간 복잡도: O(n), 배열이 최대 두 번 탐색되기 때문입니다.
- 공간 복잡도: O(1), 소수의 변수만 사용하므로
이 솔루션은 2포인터 기술을 사용하여 배열을 정렬하기 위해 제거할 가장 짧은 하위 배열을 효율적으로 찾고, 최대 10^5 요소 제약 조건까지 큰 배열을 처리합니다.
연락처 링크
이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!
이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.
- 링크드인
- 깃허브
위 내용은 배열을 정렬하기 위해 제거할 가장 짧은 하위 배열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

Video Face Swap
완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

PHP에서 Password_hash 및 Password_Verify 기능을 사용하여 보안 비밀번호 해싱을 구현해야하며 MD5 또는 SHA1을 사용해서는 안됩니다. 1) Password_hash는 보안을 향상시키기 위해 소금 값이 포함 된 해시를 생성합니다. 2) Password_verify 암호를 확인하고 해시 값을 비교하여 보안을 보장합니다. 3) MD5 및 SHA1은 취약하고 소금 값이 부족하며 현대 암호 보안에는 적합하지 않습니다.

PHP와 Python은 각각 고유 한 장점이 있으며 프로젝트 요구 사항에 따라 선택합니다. 1.PHP는 웹 개발, 특히 웹 사이트의 빠른 개발 및 유지 보수에 적합합니다. 2. Python은 간결한 구문을 가진 데이터 과학, 기계 학습 및 인공 지능에 적합하며 초보자에게 적합합니다.

PHP는 전자 상거래, 컨텐츠 관리 시스템 및 API 개발에 널리 사용됩니다. 1) 전자 상거래 : 쇼핑 카트 기능 및 지불 처리에 사용됩니다. 2) 컨텐츠 관리 시스템 : 동적 컨텐츠 생성 및 사용자 관리에 사용됩니다. 3) API 개발 : 편안한 API 개발 및 API 보안에 사용됩니다. 성능 최적화 및 모범 사례를 통해 PHP 애플리케이션의 효율성과 유지 보수 성이 향상됩니다.

PHP 유형은 코드 품질과 가독성을 향상시키기위한 프롬프트입니다. 1) 스칼라 유형 팁 : PHP7.0이므로 int, float 등과 같은 기능 매개 변수에 기본 데이터 유형을 지정할 수 있습니다. 2) 반환 유형 프롬프트 : 기능 반환 값 유형의 일관성을 확인하십시오. 3) Union 유형 프롬프트 : PHP8.0이므로 기능 매개 변수 또는 반환 값에 여러 유형을 지정할 수 있습니다. 4) Nullable 유형 프롬프트 : NULL 값을 포함하고 널 값을 반환 할 수있는 기능을 포함 할 수 있습니다.

PHP는 여전히 역동적이며 현대 프로그래밍 분야에서 여전히 중요한 위치를 차지하고 있습니다. 1) PHP의 단순성과 강력한 커뮤니티 지원으로 인해 웹 개발에 널리 사용됩니다. 2) 유연성과 안정성은 웹 양식, 데이터베이스 작업 및 파일 처리를 처리하는 데 탁월합니다. 3) PHP는 지속적으로 발전하고 최적화하며 초보자 및 숙련 된 개발자에게 적합합니다.

PHP는 주로 절차 적 프로그래밍이지만 객체 지향 프로그래밍 (OOP)도 지원합니다. Python은 OOP, 기능 및 절차 프로그래밍을 포함한 다양한 패러다임을 지원합니다. PHP는 웹 개발에 적합하며 Python은 데이터 분석 및 기계 학습과 같은 다양한 응용 프로그램에 적합합니다.

PHP와 Python은 고유 한 장점과 단점이 있으며 선택은 프로젝트 요구와 개인 선호도에 달려 있습니다. 1.PHP는 대규모 웹 애플리케이션의 빠른 개발 및 유지 보수에 적합합니다. 2. Python은 데이터 과학 및 기계 학습 분야를 지배합니다.

PHP에서 전처리 문과 PDO를 사용하면 SQL 주입 공격을 효과적으로 방지 할 수 있습니다. 1) PDO를 사용하여 데이터베이스에 연결하고 오류 모드를 설정하십시오. 2) 준비 방법을 통해 전처리 명세서를 작성하고 자리 표시자를 사용하여 데이터를 전달하고 방법을 실행하십시오. 3) 쿼리 결과를 처리하고 코드의 보안 및 성능을 보장합니다.
