検索
ホームページバックエンド開発PHPチュートリアル配列をソートするために削除される最短のサブ配列

Shortest Subarray to be Removed to Make Array Sorted

1574年。配列をソートするために削除される最短のサブ配列

難易度:

トピック: 配列、2 ポインター、二分探索、スタック、単調スタック

整数配列 arr が与えられた場合、arr 内の残りの要素が 非減少になるように、arr から部分配列 (空でもよい) を削除します。

削除する最短の部分配列の長さを返します。

サブ配列は、配列の連続したサブシーケンスです。

例 1:

  • 入力: arr = [1,2,3,10,4,2,3,5]
  • 出力: 3
  • 説明: 削除できる最も短い部分配列は、長さ 3 の [10,4,2] です。その後の残りの要素は、ソートされた [1,2,3,3,5] になります。
    • もう 1 つの正しい解決策は、サブ配列 [3,10,4] を削除することです。

例 2:

  • 入力: arr = [5,4,3,2,1]
  • 出力: 4
  • 説明: 配列は厳密に減少しているため、保持できる要素は 1 つだけです。したがって、長さ 4 の部分配列 [5,4,3,2] または [4,3,2,1] を削除する必要があります。

例 3:

  • 入力: arr = [1,2,3]
  • 出力: 0
  • 説明: 配列はすでに非減少です。要素を削除する必要はありません。

制約:

  • 1 5
  • 0 9

ヒント:

  1. 重要なのは、それぞれ最初の要素で始まるか、最後の要素で終わる最長の非減少部分配列を見つけることです。
  2. 一部の部分配列を削除すると、結果はソートされたプレフィックスとソートされたサフィックスの連結になります。ここで、プレフィックスの最後の要素はサフィックスの最初の要素よりも小さくなります。

解決策:

並べ替えと二分探索手法を使用できます。計画は次のとおりです:

アプローチ:

  1. 2 つの指針がアプローチします:

    • まず、最長の非減少プレフィックス (左ポインター) を特定します。
    • 次に、最長の非減少接尾辞 (右ポインター) を特定します。
    • その後、配列の中央部分を考慮し、結合された配列が減少しないように削除する部分配列を調整して、これら 2 つの部分配列を結合してみます。
  2. 単調スタック:

    • 単調スタックを使用すると、ソートされた方法で部分配列要素を管理できます。
  3. 手順:

    • 最長の非減少プレフィックス (左) を見つけます。
    • 最長の非減少接尾辞 (右) を見つけます。
    • 有効な組み合わせを形成できる要素を探して、2 つの部分配列をマージしてみます。
  4. 最適化:

    • 二分探索を使用して、削除する最小の部分配列を見つけるためのマージ ステップを最適化します。

このソリューションを PHP で実装してみましょう: 1574。配列をソートするために削除される最短のサブ配列

<?php /**
 * @param Integer[] $arr
 * @return Integer
 */
function shortestSubarrayToRemove($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo shortestSubarrayToRemove([1, 2, 3, 10, 4, 2, 3, 5]) . "\n"; // Output: 3
echo shortestSubarrayToRemove([5, 4, 3, 2, 1]) . "\n";           // Output: 4
echo shortestSubarrayToRemove([1, 2, 3]) . "\n";                 // Output: 0
?>

説明:

  1. 最長の減少しないプレフィックスとサフィックス:

    • プレフィックスは、要素が非降順になるまで配列を最初から走査することによって決定されます。
    • 同様に、接尾辞は末尾からのトラバースによって決定されます。
  2. 初期最小削除:

    • プレフィックスまたはサフィックスのみを保持して、削除の長さを計算します。
  3. プレフィックスとサフィックスのマージ:

    • 2 つのポインター (接頭辞の i と接尾辞の j) を使用して、接頭辞の最後の要素が接尾辞の最初の要素以下になるように削除する最小の部分配列を見つけます。
  4. 結果を返す:

    • 結果は、最初の削除またはプレフィックスとサフィックスのマージの小さい方として計算された、削除するサブ配列の最小長です。

複雑

  • 時間計算量: O(n)、配列は最大 2 回走査されるため。
  • 空間複雑度: O(1)、少数の変数のみが使用されるため。

このソリューションは、2 ポインター手法を使用して配列をソートするために削除する最短の部分配列を効率的に見つけ、10^5 要素の制約までの大きな配列を処理します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

  • LinkedIn
  • GitHub

以上が配列をソートするために削除される最短のサブ配列の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
11ベストPHP URLショートナースクリプト(無料およびプレミアム)11ベストPHP URLショートナースクリプト(無料およびプレミアム)Mar 03, 2025 am 10:49 AM

多くの場合、キーワードと追跡パラメーターで散らかった長いURLは、訪問者を阻止できます。 URL短縮スクリプトはソリューションを提供し、ソーシャルメディアやその他のプラットフォームに最適な簡潔なリンクを作成します。 これらのスクリプトは、個々のWebサイトにとって価値があります

Instagram APIの紹介Instagram APIの紹介Mar 02, 2025 am 09:32 AM

2012年のFacebookによる有名な買収に続いて、Instagramはサードパーティの使用のために2セットのAPIを採用しました。これらはInstagramグラフAPIとInstagram Basic Display APIです。

Laravelでフラッシュセッションデータを使用しますLaravelでフラッシュセッションデータを使用しますMar 12, 2025 pm 05:08 PM

Laravelは、直感的なフラッシュメソッドを使用して、一時的なセッションデータの処理を簡素化します。これは、アプリケーション内に簡単なメッセージ、アラート、または通知を表示するのに最適です。 データは、デフォルトで次の要求のためにのみ持続します。 $リクエスト -

LaravelのバックエンドでReactアプリを構築する:パート2、ReactLaravelのバックエンドでReactアプリを構築する:パート2、ReactMar 04, 2025 am 09:33 AM

これは、LaravelバックエンドとのReactアプリケーションの構築に関するシリーズの2番目と最終部分です。シリーズの最初の部分では、基本的な製品上場アプリケーションのためにLaravelを使用してRESTFUL APIを作成しました。このチュートリアルでは、開発者になります

Laravelテストでの簡略化されたHTTP応答のモッキングLaravelテストでの簡略化されたHTTP応答のモッキングMar 12, 2025 pm 05:09 PM

Laravelは簡潔なHTTP応答シミュレーション構文を提供し、HTTP相互作用テストを簡素化します。このアプローチは、テストシミュレーションをより直感的にしながら、コード冗長性を大幅に削減します。 基本的な実装は、さまざまな応答タイプのショートカットを提供します。 Illuminate \ support \ facades \ httpを使用します。 http :: fake([[ 'google.com' => 'hello world'、 'github.com' => ['foo' => 'bar']、 'forge.laravel.com' =>

PHPのカール:REST APIでPHPカール拡張機能を使用する方法PHPのカール:REST APIでPHPカール拡張機能を使用する方法Mar 14, 2025 am 11:42 AM

PHPクライアントURL(CURL)拡張機能は、開発者にとって強力なツールであり、リモートサーバーやREST APIとのシームレスな対話を可能にします。尊敬されるマルチプロトコルファイル転送ライブラリであるLibcurlを活用することにより、PHP Curlは効率的なexecuを促進します

Codecanyonで12の最高のPHPチャットスクリプトCodecanyonで12の最高のPHPチャットスクリプトMar 13, 2025 pm 12:08 PM

顧客の最も差し迫った問題にリアルタイムでインスタントソリューションを提供したいですか? ライブチャットを使用すると、顧客とのリアルタイムな会話を行い、すぐに問題を解決できます。それはあなたがあなたのカスタムにより速いサービスを提供することを可能にします

2025 PHP状況調査の発表2025 PHP状況調査の発表Mar 03, 2025 pm 04:20 PM

2025 PHP Landscape Surveyは、現在のPHP開発動向を調査しています。 開発者や企業に洞察を提供することを目的とした、フレームワークの使用、展開方法、および課題を調査します。 この調査では、現代のPHP Versioの成長が予想されています

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

PhpStorm Mac バージョン

PhpStorm Mac バージョン

最新(2018.2.1)のプロフェッショナル向けPHP統合開発ツール

Dreamweaver Mac版

Dreamweaver Mac版

ビジュアル Web 開発ツール

SecLists

SecLists

SecLists は、セキュリティ テスターの究極の相棒です。これは、セキュリティ評価中に頻繁に使用されるさまざまな種類のリストを 1 か所にまとめたものです。 SecLists は、セキュリティ テスターが必要とする可能性のあるすべてのリストを便利に提供することで、セキュリティ テストをより効率的かつ生産的にするのに役立ちます。リストの種類には、ユーザー名、パスワード、URL、ファジング ペイロード、機密データ パターン、Web シェルなどが含まれます。テスターはこのリポジトリを新しいテスト マシンにプルするだけで、必要なあらゆる種類のリストにアクセスできるようになります。

DVWA

DVWA

Damn Vulnerable Web App (DVWA) は、非常に脆弱な PHP/MySQL Web アプリケーションです。その主な目的は、セキュリティ専門家が法的環境でスキルとツールをテストするのに役立ち、Web 開発者が Web アプリケーションを保護するプロセスをより深く理解できるようにし、教師/生徒が教室環境で Web アプリケーションを教え/学習できるようにすることです。安全。 DVWA の目標は、シンプルでわかりやすいインターフェイスを通じて、さまざまな難易度で最も一般的な Web 脆弱性のいくつかを実践することです。このソフトウェアは、

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

このプロジェクトは osdn.net/projects/mingw に移行中です。引き続きそこでフォローしていただけます。 MinGW: GNU Compiler Collection (GCC) のネイティブ Windows ポートであり、ネイティブ Windows アプリケーションを構築するための自由に配布可能なインポート ライブラリとヘッダー ファイルであり、C99 機能をサポートする MSVC ランタイムの拡張機能が含まれています。すべての MinGW ソフトウェアは 64 ビット Windows プラットフォームで実行できます。